A - Ekiden Race Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

1 から N までの番号がつけられた N 人の人がある地点間を往復するレースを行いました。このレースについて、以下の情報が残されています。

  • 往路のタイムの早い順に順位をつけると、どの 2 人のタイムも異なっており、人 i\ (1 \leq i \leq N) は i 位であった。
  • 往復のタイム（往路のタイムと復路のタイムの合計）の早い順に順位をつけると、どの 2 人のタイムも異なっており、人 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 の並べ替えである
  • 入力される数値は全て整数
  • 1 つの入力に含まれるテストケースについて、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
  • 1 つ目のテストケースでは、2 人でレースを行い、復路において人 2 が人 1 を抜かしています。この場合、復路の区間賞は人 2 に与えられます。
  • 2 つ目のテストケースでは、復路で順位が変動しておらず、どの人も復路の区間賞が与えられた可能性があります。

Score : 300 points

Problem Statement

There are N people, numbered from 1 to N, who participated in a round-trip race between two points. The following information is recorded about this race.

  • The outward times of any two people were different, and person i (1 \leq i \leq N) had the i-th fastest outward time.
  • The round-trip times (the sum of the outward and return times) of any two people were different, and person i (1 \leq i \leq N) had the P_i-th fastest round-trip time.
  • The person (or persons) with the fastest return time was awarded the fastest return award.

Here, P_1, P_2, \dots, P_N is a permutation of 1, 2, \dots, N.

How many people could have received the fastest return award?

There are T test cases. Answer each of them.

Constraints

  • 1 \leq T \leq 500
  • 2 \leq N \leq 10^3
  • P_1, P_2, \dots, P_N is a permutation of 1, 2, \dots, N.
  • All input values are integers.
  • The sum of N over all test cases in a single input is at most 10^3.

Input

The input is given from Standard Input in the following format:

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

Each test case, \mathrm{case}_i\ (1 \leq i \leq T), is given in the following format:

N
P_1 P_2 \cdots P_N

Output

Print T lines. The i-th line (1 \leq i \leq T) should contain the answer for the i-th test case.

Sample Input 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

Sample Output 1

1
4
7
  • In the first test case, two people participated in the race, and person 2 overtook person 1 on the return leg. In this case, the fastest return award is awarded to person 2.
  • In the second test case, the rankings did not change on the return leg, so any person could have received the fastest return award.