Ekiden Race

时间限制：2s
空间限制：1024MB

题目描述

有 $N$ 名选手参加往返赛，编号为 $1$ 到 $N$。去程用时互不相同，选手 $i$ 的去程排名为第 $i$ 名；往返总用时也互不相同，选手 $i$ 的总排名为第 $P_i$ 名，其中 $P$ 是 $1$ 到 $N$ 的一个排列。返程用时最短的所有选手都可以获得返程区间奖。

求有多少名选手可能获得返程区间奖。共有 $T$ 组测试数据。

输入格式

第一行一个整数 $T$。每组数据先给出一个整数 $N$，下一行给出排列 $P_1,P_2,\ldots,P_N$。

输出格式

对每组数据输出一行，表示可能获奖的人数。

样例输入 1

3
2
2 1
4
1 2 3 4
20
13 2 7 1 5 9 3 4 12 10 15 6 8 14 20 16 19 18 11 17

样例输出 1

1
4
7

数据范围

对于所有数据，$1\le T\le500$，$2\le N\le10^3$，$P$ 是 $1$ 到 $N$ 的排列，单个输入中所有 $N$ 的总和不超过 $10^3$。