题目描述

有 $N$ 个人参加了一场在某地点间往返的比赛，每个人编号为 $1$ 到 $N$。关于这场比赛，已知以下信息：

• 按照去程用时从快到慢排名，所有人的用时都不相同，第 $i$ 个人（$1 \leq i \leq N$）获得第 $i$ 名。
• 按照往返用时（去程用时与返程用时之和）从快到慢排名，所有人的用时也都不相同，第 $i$ 个人（$1 \leq i \leq N$）获得第 $P_i$ 名。
• 返程用时最快的人（如有多人并列则所有人）将获得返程区间奖。

这里，$P_1, P_2, \dots, P_N$ 是 $1, 2, \dots, N$ 的一个排列。

请问，有多少人有可能获得返程区间奖？

给定 $T$ 组测试数据，请分别输出答案。

输入格式

输入按以下格式从标准输入给出。

$T$
$\mathrm{case}_1$
$\vdots$
$\mathrm{case}_T$

每组测试数据 $\mathrm{case}_i\ (1 \leq i \leq T)$ 格式如下：

$N$ $P_1$ $P_2$ $\cdots$ $P_N$

输出格式

输出 $T$ 行。第 $i$ 行（$1 \leq i \leq T$）输出第 $i$ 组测试数据的答案。

样例 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
4
7

说明/提示

限制条件

• $1 \leq T \leq 500$
• $2 \leq N \leq 10^3$
• $P_1, P_2, \dots, P_N$ 是 $1, 2, \dots, N$ 的一个排列
• 输入的所有数值均为整数
• 所有测试数据中 $N$ 的总和不超过 $10^3$

样例解释 1

• 第 1 组测试数据中，有 2 个人参赛，在返程中第 2 个人超过了第 1 个人。这种情况下，返程区间奖会颁给第 2 个人。
• 第 2 组测试数据中，返程时排名没有变化，因此每个人都有可能获得返程区间奖。

由 ChatGPT 4.1 翻译