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.