← 返回题目列表

AtCoder · arc162_a

A. 接力赛

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

有 N 人,编号自 1 to 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 测试用例。逐一回答。

约束

  • 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.

输入

输入由标准输入按以下格式给出:

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

1
4
7
  • 在第一个测试用例中,两个人参加了比赛,并且一个人 2 超过了人 1 在回程航段。在这种情况下,最快回报奖授予人 2.
  • 在第二个测试用例中,回程时排名没有变化,因此任何人都可以获得最快回程奖励。