Вам дан массив \(a\), состоящий из \(n\) целых чисел. Изначально все элементы \(a\) равны \(0\) либо \(1\). Вы должны обработать \(q\) запросов двух типов:
- 1 x : Присвоить \(a_x\) значение \(1 - a_x\).
- 2 k : Вывести \(k\)-й наибольший элемент массива.
Напомним, что \(k\)-й наибольший элемент массива \(b\) определяется следующим образом:
- Сортируем массив в невозрастающем порядке, возвращаем из него \(k\)-й элемент.
Например, второй наибольший элемент массива \([0, 1, 0, 1]\) равен \(1\), так как после сортировки в невозрастающем порядке он становится равен \([1, 1, 0, 0]\), а второй элемент в этом массиве равен \(1\).
Выходные данные
Для каждого запроса второго типа выведите единственное целое число — ответ на запрос.
Примечание
Изначально \(a = [1, 1, 0, 1, 0]\).
В первой операции нужно вывести третье наибольшее значение, которое равно \(1\).
Вторая операция присваивает \(a_2\) значение \(0\), \(a\) становится \([1, 0, 0, 1, 0]\).
В третьей операции нужно вывести третье наибольшее значение, которое равно \(0\).
В четвертой операции нужно вывести первое наибольшее значение, которое равно \(1\).
В пятой операции нужно вывести пятое наибольшее значение, которое равно \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5
1 1 0 1 0
2 3
1 2
2 3
2 1
2 5
|
1
0
1
0
|