Overview

We examine the differences between adjacent board positions and find the index of the gap with the maximum width. If there are multiple gaps with the same maximum width, we select the leftmost index.

Analysis

The width of the \(i\)-th gap from the left can be calculated by the following formula:

\(A_{i+1} - A_i\)

Since there are only \(N-1\) gaps in total, it is sufficient to examine all widths sequentially. This straightforward method easily runs within the time limit, so no special optimization is required.

What requires attention is how to handle cases where multiple gaps have the maximum width. When checking from left to right, if we update the answer even when the width is equal to the current maximum, we will end up choosing a gap further to the right, resulting in an incorrect answer.

Therefore, we only update the answer when we find a width strictly greater than the current maximum width. By not updating on equal widths, the index of the leftmost gap is preserved.

For example, when the board positions are \([1, 4, 9, 14]\), the gap widths from the left are \(3, 5, 5\). The maximum width is \(5\), corresponding to the \(2\)-nd and \(3\)-rd gaps. Since we do not update on equal widths, the answer is \(2\).

Algorithm

1. Initialize using the first gap:
   • Set the maximum width best to \(A_2-A_1\).
   • Set the answer ans to \(1\).
2. Examine the \(2\)-nd through \((N-1)\)-th gaps sequentially from left to right:
   • Find the gap width w.
   • If w > best, update best to w and ans to the index of that gap.
   • Otherwise, do not update.
3. Output ans.

Throughout this process, best always represents the “maximum width among the gaps examined so far,” and ans represents the “index of the leftmost gap with that width.” Therefore, once all gaps have been checked, ans is the desired answer.

Complexity

• Time complexity: \(O(N)\)
  We examine each of the \(N-1\) gaps exactly once.
• Space complexity: \(O(N)\)
  Used to store the input board positions. The additional space required for the search itself is \(O(1)\).

Implementation Notes

• Python lists are \(0\)-indexed. In the code, a[i] - a[i - 1] corresponds to \(A_{i+1}-A_i\) in the problem statement, which is the width of the \(i\)-th gap from the left. Therefore, when updating, we set ans = i.

• Since the first gap is already processed during initialization, the loop runs over range(2, n). This corresponds to the \(2\)-nd through \((N-1)\)-th gaps.

• Use > rather than >= for the comparison so that the answer is not updated when the width is equal.

• When \(N=2\), the loop does not execute, and \(1\), the index of the only gap, is output directly.

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    ans = 1
    best = a[1] - a[0]
    for i in range(2, n):
        w = a[i] - a[i - 1]
        if w > best:
            best = w
            ans = i
    print(ans)

main()

---

This editorial was generated by gpt-6-astra-medium.