Leftmost Big Enough

Difficulty: 1900 4000 ms 128 MB

segment-tree

Support U i v (assign a_i = v) and Q x — print the SMALLEST index whose value is ≥ x, or −1.

Input: the first line has N and Q; the second line has the array; each of the next Q lines is an operation.

Output: one line per query.

Constraints:

• 1 ≤ N, Q ≤ 10⁵
• |values|, |x| ≤ 10⁶

Sample Tests

5 3
3 1 4 1 5
Q 4
U 3 0
Q 4

3
5

1 1
5
Q 6

-1

Read the Editorial