Overview

This problem asks us to find the student with the highest leadership score among those who have a higher score than the current class president (student with attendance number 1). If there are ties, we select the student with the smallest attendance number.

Analysis

Key Observations

1. Only consider students with attendance number 2 and above: Since the student with attendance number 1 is the current class president, we search for candidates among the other students.

2. There are two-stage conditions:

   • First, only students with scores strictly greater than the current president’s score \(A_1\) are candidates
   • Among those candidates, select the student with the maximum score
   • If multiple students have the same maximum score, select the one with the smallest attendance number

3. Output -1 if there are no candidates: If no student has a higher score than the current class president, no change is made.

Concrete Examples

For example, if \(N = 5\) and \(A = [50, 80, 80, 90, 70]\): - The current class president is attendance number 1 (score 50) - Students with scores greater than 50: attendance numbers 2(80), 3(80), 4(90), 5(70) - The maximum score among these is 90 (attendance number 4) - Therefore, the answer is 4

In another example, if \(N = 3\) and \(A = [100, 50, 30]\): - The current class president is attendance number 1 (score 100) - Students with scores greater than 100: none - Therefore, the answer is -1

Algorithm

1. Record the current class president’s leadership score \(A_1\)
2. Examine students from attendance number 2 to \(N\) in order
3. For each student:
   • Check if their score is greater than \(A_1\)
   • If so, compare with the current maximum score
     • If greater, update the maximum score and attendance number
     • If equal, keep the smaller attendance number
4. Finally, output the attendance number if a candidate was found, otherwise output -1

current_president_score = A[0]
max_score = -1
answer_attendance_number = -1

for i = 1 to N-1:
    if A[i] > current_president_score:
        if A[i] > max_score:
            max_score = A[i]
            answer_attendance_number = i + 1  # +1 because of 0-indexed
        elif A[i] == max_score:
            # Select the smaller attendance number (the one found first is smaller)
            # In this implementation, we scan from left to right so the smaller one is automatically kept

Complexity

• Time complexity: \(O(N)\)
  • The answer can be found by scanning the array just once
• Space complexity: \(O(N)\)
  • Space needed to store the input array

Implementation Notes

1. Converting between 0-indexed and 1-indexed: Arrays are managed as 0-indexed, but attendance numbers are 1-indexed, so we need to output i + 1.

2. Handling ties: Since we scan from left to right, when we find students with the same score, we simply keep the one found first (the one with the smaller attendance number). In the code, we check i + 1 < max_index when A[i] == max_score, but since we’re scanning from left to right, this condition will never actually be true (it can be omitted for more concise code).

3. Initial value settings: By setting max_score = -1, the algorithm works correctly under the constraint that scores are at least 1.

   Source Code

N = int(input())
A = list(map(int, input().split()))

current_leader_score = A[0]

max_score = -1
max_index = -1

for i in range(1, N):
    if A[i] > current_leader_score:
        if A[i] > max_score:
            max_score = A[i]
            max_index = i + 1
        elif A[i] == max_score:
            if i + 1 < max_index:
                max_index = i + 1

if max_index == -1:
    print(-1)
else:
    print(max_index)

This editorial was generated by claude4.5opus.