Overview

Given the management numbers \(A_i\) of \(N\) books lined up on a bookshelf, find the “leftmost position” of a book whose value is exactly \(K\), or output \(-1\) if none exists.

Analysis

What we want to find is not just “whether it exists,” but “if it exists, the minimum position (how many positions from the left).”
From this condition, we can scan from left to right, and the moment we first find \(K\), that is confirmed to be the minimum position.

For example, when \(A = [3, 5, 2, 5],\ K=5\), scanning from left to right: - 1st: 3 (no match) - 2nd: 5 (match) → This is the minimum position, so the answer is 2

In this way, once we find a match partway through, there is no need to search further (we can terminate early).

Since the constraint is \(N \le 2 \times 10^5\), an \(O(N)\) approach that scans \(A\) from the beginning once is more than sufficient.
On the other hand, a method that sorts and then uses binary search would be inappropriate, as it destroys the minimum “position” (the ordering changes). Additionally, sorting costs \(O(N \log N)\), which is unnecessary.

Algorithm

1. Scan the array \(A\) from left to right.
2. If the element \(A_i\) at position \(i\) (1-indexed) equals \(K\), output \(i\) at that point and terminate.
3. If no match is found by the end, output \(-1\).

Complexity

• Time complexity: \(O(N)\) (at most \(N\) comparisons)
• Space complexity: \(O(1)\) (almost no additional space used beyond the input array)

Implementation Notes

• Since we want to find the “minimum position,” it is important to scan from left to right and terminate immediately upon the first match.

• The output position is 1-indexed, so in Python, using enumerate(A, 1) prevents off-by-one errors.

• Since the input may be large, using sys.stdin.readline ensures stability.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    for i, x in enumerate(A, 1):
        if x == K:
            print(i)
            return
    print(-1)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.