Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Hossam and Combinatorics

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHossam woke up bored, so he decided to create an interesting array with his friend Hazem.

Now, they have an array $$$a$$$ of $$$n$$$ positive integers, Hossam will choose a number $$$a_i$$$ and Hazem will choose a number $$$a_j$$$.

Count the number of interesting pairs $$$(a_i, a_j)$$$ that meet all the following conditions:

- $$$1 \le i, j \le n$$$;
- $$$i \neq j$$$;
- The absolute difference $$$|a_i - a_j|$$$ must be equal to the maximum absolute difference over all the pairs in the array. More formally, $$$|a_i - a_j| = \max_{1 \le p, q \le n} |a_p - a_q|$$$.

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$), which denotes the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^5$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case print an integer — the number of interesting pairs $$$(a_i, a_j)$$$.

Example

Input

256 2 3 8 167 2 8 3 2 10

Output

2 4

Note

In the first example, the two ways are:

- Hossam chooses the fourth number $$$8$$$ and Hazem chooses the fifth number $$$1$$$.
- Hossam chooses the fifth number $$$1$$$ and Hazem chooses the fourth number $$$8$$$.

In the second example, the four ways are:

- Hossam chooses the second number $$$2$$$ and Hazem chooses the sixth number $$$10$$$.
- Hossam chooses the sixth number $$$10$$$ and Hazem chooses the second number $$$2$$$.
- Hossam chooses the fifth number $$$2$$$ and Hazem chooses the sixth number $$$10$$$.
- Hossam chooses the sixth number $$$10$$$ and Hazem chooses the fifth number $$$2$$$.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/08/2023 20:06:54 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|