sqrt декомпозиция

Костя и Женя — создатели группы <<Бумага>> — после выпуска легендарного альбома решили создать новое музыкальное объединение <<дневные грузчики>>, для этого им нужно найти двух новых людей.

Они пригласили на кастинг \(n\) человек. Кастинг продлится \(q\) дней. В \(i\)-й из дней Костя и Женя хотят найти двух человек на отрезке с \(l_i\) по \(r_i\), которые больше всего подходят их объединению. Так как <<дневные грузчики>> занимаются современным искусством,  музыкальные навыки им не важны, и они смотрят лишь на внешние признаки: им хочется, чтобы разница роста двух людей была как можно меньше.

Помогите им, и для каждого дня укажите минимальную разницу роста людей с кастинга на данном отрезке!

Формат входных данных
В первой строке вам дано два числа \(n, q\) (\(2 \leqslant n \leqslant 4 \cdot 10^5, 1 \leqslant q \leqslant 10^6\)) — количество людей, которые пришли на кастинг, а также количество дней кастинга.

Во второй строке вам даны \(n\) чисел \(a_1, a_2, a_3, \ldots, a_n\) (\(1 \leqslant a_i \leqslant n\)) — рост каждого из кандидатов.

Также гарантируется, что все \(a_i\) различны.

В следующих \(q\) строках даны по \(2\) числа \(l_i, r_i\) (\(1 \leqslant l_i < r_i \leqslant n\)) — отрезок людей для рассмотрения в \(i\)-й день кастинга.

Формат выходных данных
Выведите \(q\) строк. В \(i\)-й строке должна быть минимальная разница роста между двумя кандидатами на отрезке в \(i\)-й день кастинга.

Примечание
В первом примере минимальная разность на отрезке \([1, 2]\) составляет \(2\) (\(3 - 1 = 2\)), на отрезке \([2, 3]\) – \(1\), на отрезке \([1, 3]\) также \(1\).

В третьем примере минимальную разность на отрезке \([4, 6]\) составляют числа \(3, 5\) (\(5 - 3 = 2\)). На отрезке \([1, 2]\) минимальную разность имеют числа \(2, 6\) (\(6 - 2 = 0\)). На отрезке \([3, 6]\) минимальную разность имеют числа \(1, 3\) (\(3 - 1 = 2\)). На отрезке \([1, 3]\) минимальную разность образуют числа \(1, 2\) (\(2 - 1 = 1\)).

На курсе машинного обучения вам выдали первое домашнее задание — вам предстоит проанализировать некоторый массив из \(n\) чисел.

В частности, вы интересуетесь так называемой равномерностью массива. Предположим, что в массиве число \(b_1\) встречается \(k_1\) раз, \(b_2\) — \(k_2\) раз, и т.д. Тогда равномерностью массива называется такое минимальное целое число \(c \ge 1\), что \(c \ne k_i\) для любого \(i\).

В рамках вашего исследования вы хотите последовательно проделать \(q\) операций.

• Операция \(t_i = 1\), \(l_i\), \(r_i\) задаёт запрос исследования. Необходимо вывести равномерность массива, состоящего из элементов на позициях от \(l_i\) до \(r_i\) включительно.

• Операция \(t_i = 2\), \(p_i\), \(x_i\) задаёт запрос уточнения данных. Начиная с этого момента времени \(p_i\)-му элементу массива присваивается значения \(x_i\).

Формат входных данных
Первая строка содержит \(n\) и \(q\) (\(1 \le n, q \le 100\,000\)) — размер массива и число запросов соответственно.

Во второй строке записаны ровно \(n\) чисел — \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\(1 \le a_i \le 10^9\)).

Каждая из оставшихся \(q\) строк задаёт очередной запрос.

Запрос первого типа задаётся тремя числами \(t_i = 1\), \(l_i\), \(r_i\), где \(1 \le l_i \le r_i \le n\) — границы соответствующего отрезка.

Запрос второго типа задаётся тремя числами \(t_i = 2\), \(p_i\), \(x_i\), где \(1 \le p_i \le n\) — позиция в которой нужно заменить число, а \(1 \le x_i \le 10^9\) — его новое значение

Формат выходных данных
Для каждого запроса первого типа выведите одно число — равномерность соответствующего отрезка массива.

Первый запрос состоит из ровно одного элемента — \(1\). Минимальное подходящее \(c = 2\).

Отрезок второго запроса состоит из четырёх \(2\), одной \(3\) и двух \(1\). Минимальное подходящее \(c = 3\).

Отрезок четвёртого запроса состоит из трёх \(1\), трёх \(2\) и одной \(3\). Минимальное подходящее \(c = 2\).

Дан массив a длины n (\(1 <= n <= 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида +, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)) и запросов вида ?, l, r, k (\(1 <= l <= r <= n\), \(-10^9 <= k <= 10^9\)).

В первом случае нужно добавить к числам на отрезке от l до r включительно, число k.
Во втором случае нужно вывести 1, если на отрезке от l до r включительно, есть число k, иначе вывести 0.

Элементы нумеруются с 1 до n.

Гарантируется, что после любого запроса любой элемент массива a лежит в диапазоне от \(-10^9\) до \(10^9\) включительно.

Примеры

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида *, l, r, k (\(1 <= l <= r <= n\), \(0 <= k <10\)) и запросов вида ?, i (\(1 <= i <= n\)).

В первом случае нужно умножить числа на отрезке от l до r включительно на k.

Во втором случае нужно вывести число, стоящее на позиции i.

Элементы нумеруются с 1 до n.

Примеры

Дан массив a длины n (\(1 <= n <= 2 \cdot 10^6\), \(1 <= a_i <= 10^9\)). Также даны m (\(1 <= m <= 500\)) запросов вида t, l, r (\(0 <= t <= 1\), \(1 <= l <= r <= n\)).

Если \(t = 0\), то на запрос нужно вывести сумму чисел на отрезке от l до r включительно. Если \(t = 1\), то элементу с номером l присваивается значение r. Элементы нумеруются с 1 до n. 

Примеры