Overview

We look at each shelf in order from the entrance side, maintaining a cumulative sum \(A_1 + A_2 + \cdots + A_k\) of the number of products.
We output the shelf number where the cumulative sum first reaches \(X\) or more, and output -1 if it never reaches \(X\) by the end.

Analysis

What we want to find is the first position where the cumulative sum becomes \(X\) or more.

For example, when
\(A = [2, 3, 1, 5, 4]\), \(X = 10\), the cumulative sums are:

• Up to the 1st shelf: \(2\)
• Up to the 2nd shelf: \(2+3=5\)
• Up to the 3rd shelf: \(2+3+1=6\)
• Up to the 4th shelf: \(2+3+1+5=11\)

The first time it reaches \(10\) or more is at the 4th shelf.

Naive Approach

If we compute \(A_1 + A_2 + \cdots + A_k\) from scratch for each \(k\),
the total cost is

\[ 1 + 2 + 3 + \cdots + N = O(N^2) \]

Since \(N \leq 5 \times 10^5\), \(O(N^2)\) is too slow.

How to Improve

If we keep the running total of the shelves seen so far in a variable s, then each time we move to the next shelf, we simply update:

\[ s \leftarrow s + A_i \]

This way, we only look at each shelf once, so the overall complexity is \(O(N)\).

Algorithm

1. Initialize the cumulative sum s = 0.
2. Look at shelves in order starting from the 1st.
3. For each shelf \(i\), perform s += A_i.
4. If s >= X, output the current shelf number \(i\) and terminate.
5. If s >= X is never satisfied after examining all shelves, output -1.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Shelf numbers are 1-indexed, so using enumerate(A, 1) directly gives the correct shelf number as the answer.

• Once the condition is met, immediately print(i) and return to avoid unnecessary processing.

• \(X\) can be as large as \(10^{15}\), but Python’s integer type handles this safely without overflow.

• This implementation uses sys.stdin.buffer.read() for fast input, which is effective given the large constraints.

  Source Code

import sys

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

    s = 0
    for i, a in enumerate(A, 1):
        s += a
        if s >= X:
            print(i)
            return
    print(-1)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.