Editorial

Approach

The area of villager \(i\)’s field is \(A_i \times B_i\). Scan the villagers in order \(i = 1, 2, \dots, N\), keeping track of the maximum area seen so far and the index of the villager who achieved it.

Update the answer only when the current area is strictly greater than the recorded maximum. This guarantees that if multiple villagers share the same maximum area, the one encountered first — i.e., the one with the smallest index — is retained, which automatically satisfies the tie-breaking rule.

Pseudocode

bestArea ← -1
best ← 0
for i = 1 to N:
    area ← A_i × B_i
    if area > bestArea:
        bestArea ← area
        best ← i
print best

Proof of Correctness

Claim: When the algorithm terminates, best is the smallest index among villagers with the maximum area.

Proof: We show the loop invariant: “after processing villager \(i\), bestArea equals the maximum of \(A_1 B_1, \dots, A_i B_i\), and best is the smallest index achieving that maximum.”

• Initialization: Before the loop, bestArea = -1 acts as the maximum over an empty set. Since \(A_i, B_i \geq 1\), every area is at least \(1\), so the invariant holds vacuously.
• Maintenance: When processing villager \(i\), if \(A_i B_i > \text{bestArea}\), then \(i\) is the unique index holding the new maximum, so setting best ← i preserves the invariant. If \(A_i B_i \leq \text{bestArea}\), the maximum is unchanged; even when \(A_i B_i = \text{bestArea}\), the existing best has a smaller index (since \(i\) is processed later), so not updating is correct.
• Termination: When the loop ends at \(i = N\), the invariant implies best is the smallest-indexed villager with the maximum area among all villagers.

Complexity

• Time: \(O(N)\), including reading the input.
• Space: \(O(1)\) for C++ and \(O(N)\) for Python, including stored input and output arrays or strings.