A14116. K-th Largest Value

You are given an array $a$ consisting of $n$ integers. Initially all elements of $a$ are either $0$ or $1$ . You need to process $q$ queries of two kinds:

- 1 x : Assign to $a_x$ the value $1 - a_x$ .
- 2 k : Print the $k$ -th largest value of the array.

As a reminder, $k$ -th largest value of the array $b$ is defined as following:

- Sort the array in the non-increasing order, return $k$ -th element from it.

For example, the second largest element in array $[0, 1, 0, 1]$ is $1$ , as after sorting in non-increasing order it becomes $[1, 1, 0, 0]$ , and the second element in this array is equal to $1$ .

The first line contains two integers $n$ and $q$ ( $1 \le n, q \le 10^5$ ) — the length of the given array and the number of queries.

The second line contains $n$ integers $a_1, a_2, a_3, \dots, a_n$ ( $0 \le a_i \le 1$ ) — elements of the initial array.

Each of the following $q$ lines contains two integers. The first integer is $t$ ( $1 \le t \le 2$ ) — the type of query.

- If $t = 1$ the second integer is $x$ ( $1 \le x \le n$ ) — the position of the modified number. You have to assign to $a_x$ the value $1 - a_x$ .
- If $t = 2$ the second integer is $k$ ( $1 \le k \le n$ ) — you need to print the $k$ -th largest value of the array.

It's guaranteed that there will be at least one query of the second type (satisfying $t = 2$ ).

For each query of the second type, print a single integer — the answer to the query.

Initially $a = [1, 1, 0, 1, 0]$ .

The first operation is printing the third largest value, which is $1$ .

The second operation is assigning $a_2$ the value $0$ , $a$ becomes $[1, 0, 0, 1, 0]$ .

The third operation is printing the third largest value, it is $0$ .

The fourth operation is printing the first largest value, it is $1$ .

The last operation is printing the fifth largest value, it is $0$ .