Динамический массив
Требуется реализовать структуру данных, которая представляет из себя динамический массив, поддерживающий следующие операции:
Присвоить числу, которое стоит на позиции u, значение p.
Вставить число p после позиции u (но перед позицией u+1, если она существует).
Сообщить, сколько чисел, не превосходящих p, стоит на позициях с u по v включительно.
Элементы массива нумеруются с единицы.
Входные данные
В первой строке находятся два натуральных числа n и m - начальное количество элементов в массиве и количество операций (1 ≤ n ≤ 200000, 1 ≤ m ≤ 200000). Во второй строке находится n целых чисел a_1, a_2, ..., a_n - элементы исходного массива (0 ≤ a_i ≤ 10^6). Следующие m строк содержат описания операций в формате
1 u p (u ≥ 1, u не превосходит текущего размера массива, 0 ≤ p ≤ 10^6),
2 u p (u ≥ 0, u не превосходит текущего размера массива, 0 ≤ p ≤ 10^6)
или
3 u v p (1 ≤ u ≤ v, v не превосходит текущего размера массива, 0 ≤ p ≤ 10^6).
Выходные данные
В выходном файле должны находиться ответы на запросы - по одному в строке.