Задача: Глеб и медиана

Глеб устал от побитового исключающего <<или>> и решил, что пора найти новую интересную функцию. Его выбор пал на медиану. Напомним, медианой массива называется число, которое окажется посередине, если массив упорядочить по возрастанию. В рамках этой задачи для массивов чётной длины положим медиану равной левому из двух центральных в отсортированном порядке элементов.

Для некоторого числа \(m\) назовём \(m\)-разбиением массива такое его разбиение на непересекающиеся отрезки, что на каждом из этих отрезков медиана больше либо равна \(m\). Вам дан массив \(a\) длины \(n\) и \(q\) запросов двух видов:

1. присвоить элементу с индексом \(i\) значение \(x\);

2. найти наибольшее число \(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 групп:

1. \(n \le 5, q \le 5\), такие решения будут набирать не менее 10% баллов

2. \(n \le 100, q \le 100\), такие решения будут набирать не менее 20% баллов

3. \(n \le 10000, q \le 10000\), такие решения будут набирать не менее 30% баллов

4. \(m\) - одно и тоже для всех запросов, такие решения будут набирать не менее 25% баллов

5. нет запросов изменения, такие решения будут набирать не менее 35% баллов

6. Ограничения, как и в задаче

Ваш ответ: