B - Election of the Class President Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は学校の先生で、クラスの委員長選出を担当しています。クラスには N 人の生徒が所属しており、各生徒には 1 から N までの出席番号が付けられています。生徒 i のリーダーシップ点数は A_i です。

現在、出席番号 1 の生徒が暫定的にクラス委員長として登録されています。高橋君は、現在の委員長以外の生徒の中に現在の委員長よりもリーダーシップ点数が真に大きい生徒がいる場合、委員長を変更します。

具体的には、高橋君は以下のルールに従います：

  1. 現在の委員長（出席番号 1 の生徒）よりもリーダーシップ点数が真に大きい生徒が 1 人以上存在する場合、それらの生徒の中で最もリーダーシップ点数が高い生徒を新しい委員長に指名します。最もリーダーシップ点数が高い生徒が複数いる場合は、その中で出席番号が最も小さい生徒を選びます。
  2. 現在の委員長よりもリーダーシップ点数が真に大きい生徒が存在しない場合、委員長の変更は行いません。

高橋君が委員長の変更を行った場合は新しい委員長の出席番号を、変更を行わなかった場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、生徒の人数を表す整数 N が与えられる。
  • 2 行目には、各生徒のリーダーシップ点数を表す整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。A_i は出席番号 i の生徒のリーダーシップ点数である。

出力

委員長の変更を行った場合は新しい委員長の出席番号を、変更を行わなかった場合は -1 を 1 行で出力せよ。

入力例 1

5
3 7 5 7 2

出力例 1

2

入力例 2

4
10 5 8 3

出力例 2

-1

入力例 3

10
50 120 80 120 90 150 150 30 100 75

出力例 3

6

Score : 233 pts

Problem Statement

Takahashi is a school teacher in charge of selecting the class representative. There are N students in the class, and each student is assigned an attendance number from 1 to N. The leadership score of student i is A_i.

Currently, the student with attendance number 1 is provisionally registered as the class representative. Takahashi will change the representative if there exists a student other than the current representative whose leadership score is strictly greater than that of the current representative.

Specifically, Takahashi follows the rules below:

  1. If there exists one or more students whose leadership score is strictly greater than that of the current representative (the student with attendance number 1), the student with the highest leadership score among them is appointed as the new representative. If there are multiple students with the highest leadership score, the one with the smallest attendance number is chosen.
  2. If there is no student whose leadership score is strictly greater than that of the current representative, the representative is not changed.

If Takahashi changed the representative, output the attendance number of the new representative. If no change was made, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • All inputs are integers.

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N, representing the number of students.
  • The second line contains integers A_1, A_2, \ldots, A_N separated by spaces, representing the leadership scores of each student. A_i is the leadership score of the student with attendance number i.

Output

If the representative was changed, output the attendance number of the new representative. If no change was made, output -1 on a single line.

Sample Input 1

5
3 7 5 7 2

Sample Output 1

2

Sample Input 2

4
10 5 8 3

Sample Output 2

-1

Sample Input 3

10
50 120 80 120 90 150 150 30 100 75

Sample Output 3

6