Overview

Given the score of the student with attendance number \(1\) (the current class leader), if there exists a student with a strictly higher leadership score, output the number of the student with the highest score among them (in case of a tie, the one with the smallest attendance number). If no such student exists, output \(-1\).

Analysis

The key point is that the comparison is only against the score \(A_1\) of the “current class leader (attendance number \(1\)).” In other words, we need to find “the maximum \(A_i\) among students satisfying \(A_i > A_1\) (and the smallest \(i\) in case of a tie).”

A single pass through all students is sufficient for this. For example, if \(A = [5, 6, 6, 4, 7]\), the baseline is \(A_1 = 5\), and the values greater than \(5\) are \(6, 6, 7\). The maximum is \(7\), so we output attendance number \(5\). If \(A = [5, 6, 6, 4]\), the maximum is \(6\) and there are multiple students with the same score, so we output attendance number \(2\), which is the smallest.

A naive approach like “collect all students satisfying the condition and sort them” also works, but sorting takes \(O(N \log N)\). While this is fast enough for the constraint of at most \(2 \times 10^5\), it involves unnecessary computation. A single scan achieves \(O(N)\).

Algorithm

1. Store the baseline score \(base = A_1\).
2. Prepare variables best_score (the highest score found so far) and best_idx (its attendance number), initialized to -1 to indicate “not found.”
3. Iterate from \(i = 2\) to \(N\) (in 0-indexed implementation: for i in range(1, N)).
   • If \(A_i > base\), the student is a candidate.
   • If the candidate’s score is greater than best_score, update.
   • If tied (\(A_i == best_score\)), adopt the one with the smaller attendance number (update if idx < best_idx).
4. At the end, if best_idx has been updated, output it; otherwise, output \(-1\).

Complexity

• Time complexity: \(O(N)\) (a single pass through all students)
• Space complexity: \(O(1)\) (only a constant number of variables, excluding the input array)

Implementation Notes

• Since the condition requires “strictly greater,” the check must be \(A_i > A_1\) (not \(A_i \ge A_1\)).

• For tie-breaking, we need to select “the one with the smallest attendance number,” so we must track not only the maximum value but also its corresponding attendance number.

• In Python, when input is large, using sys.stdin.buffer.read() allows for faster reading.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N = data[0]
    A = data[1:]

    base = A[0]
    best_score = -1
    best_idx = -1

    for i in range(1, N):
        if A[i] > base:
            idx = i + 1
            if A[i] > best_score or (A[i] == best_score and idx < best_idx):
                best_score = A[i]
                best_idx = idx

    print(best_idx if best_idx != -1 else -1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.