micro-and-something-more

After figuring out what was that something that was bothering him, something more started bothering Micro. See, Micro's a kind of guy, who always has something bothering him. This time his friend Chacha will help him find out if he passes the "Test". Chacha gave him an array A having N integers. Now Chacha will ask Q queries. Each query will be of one of the following types:

0 x val: Set A[x] = val
1 val: Find position of first element in the array that is greater than or equal to val.

Assume 1-based indexing of the array.Help Micro perform the queries.

Input:
First line of input consists of two space separated integers denoting N and Q.
Second line consists of N space separated integers denoting the array A.
Following Q lines consists of query as described in the statement.

Output:
For each query of type 1 print the answer in a new line.

Constraints:
1 ≤ N, Q, x ≤ 10^5 
1 ≤ A[i], val ≤ 10^9

SAMPLE INPUT
5 4
5 4 3 2 1
1 4
1 6
0 3 7
1 6

SAMPLE OUTPUT
1
-1
3

Source: hackerearth | Difficulty: EASY
Tags: Range queries

Segment trees revisited


Solutions: