Глеб устал от побитового исключающего <<или>> и решил, что пора найти новую интересную функцию. Его выбор пал на медиану. Напомним, медианой массива называется число, которое окажется посередине, если массив упорядочить по возрастанию. В рамках этой задачи для массивов чётной длины положим медиану равной левому из двух центральных в отсортированном порядке элементов.
Для некоторого числа \(m\) назовём \(m\)-разбиением массива такое его разбиение на непересекающиеся отрезки, что на каждом из этих отрезков медиана больше либо равна \(m\). Вам дан массив \(a\) длины \(n\) и \(q\) запросов двух видов:
-
присвоить элементу с индексом \(i\) значение \(x\);
-
найти наибольшее число \(k\) такое, что для подотрезка массива с индексами от \(l\) до \(r\) существует \(m\)-разбиение на \(k\) отрезков.
Формат входных данных
В первой строке дается число \(n\) (\(1 \le n \le 2 \cdot 10^5\)) - размер массива. В следующей строке вводятся \(n\) чисел \(a_{i}\) (\(1 \le a_{i} \le 10^9\)) - элементы массива, на следующей строке вводится число \(q\) (\(1 \le q \le 2 \cdot 10^5\)) - количество запросов. В следующих \(q\) строках даются запросы, каждый в одном из следующих форматов:
-
\(1\) \(i\) \(x\) — запрос 1 типа (\(1 \le i \le n, 1 \le x \le 10^9\));
-
\(2\) \(m\) \(l\) \(r\) — запрос 2 типа (\(1 \le m \le 10^9, 1 \le l \le r \le n\)).
Формат выходных данных
Для каждого запроса второго типа в отдельной строке выведите ответ на запрос. В случае если для отрезка не существует никакого \(m\)-разбиения, выведите \(0\).
В задаче присутствуют 6 групп:
-
\(n \le 5, q \le 5\), такие решения будут набирать не менее 10% баллов
-
\(n \le 100, q \le 100\), такие решения будут набирать не менее 20% баллов
-
\(n \le 10000, q \le 10000\), такие решения будут набирать не менее 30% баллов
-
\(m\) - одно и тоже для всех запросов, такие решения будут набирать не менее 25% баллов
-
нет запросов изменения, такие решения будут набирать не менее 35% баллов
-
Ограничения, как и в задаче
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 5
4
2 2 1 3
1 1 5
2 5 1 5
2 4 4 5
|
1
0
2
|