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

Для некоторого числа $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$.

Подзадачи