Limits 500ms, 512 MB

International University of Turkey (IUT) is organizing its annual sports tournament. Students from different departments participate in this tournament. If a student gets top position in an event, he/she will get points. The student that gets the highest point wins the most prestigious Organization of International Competitions (OIC) gold medal. If multiple students get the highest point, all of them will get a gold medal!

In this tournament, among different events, a special attraction is 5000 m race. Pretty tiring, ain't it? For this reason, this event is held at the end of the tournament. The rules of this race are the following:

  • N students participate in the race.
  • The student who becomes first will earn NN points. The second-placed student will earn N-1 points and so on.
  • There will be no tie.

You are the sports co-ordinator. You kept track of the points of each student throughout the tournament. You want to find out how many students have the chance to win the OIC gold medal. Be careful! Since there's a gold medal at stake, lots of students will participate.

Input

The first line of input will contain T (1 <= T <= 10) the number of test cases. For each case, there will a single integer, N (3 <= N <= 300000) denoting the total number of students that are participating. The next line will contain N positive space-separated integers (0 <= scores <= 2000000), describing the score of each student.

Output

For each test case, print a single integer denoting the answer. Print a newline after each output.

Sample

InputOutput
1
3
1 2 3
3

Submit

Login to submit.

Statistics

32% Solution Ratio
erfanul007Earliest, Oct '19
nusuBotFastest, 0.0s
blizzardLightest, 1.3 MB
blizzardShortest, 561B
Toph uses cookies. By continuing you agree to our Cookie Policy.