Задача J. (20081225) Динамический массив ≡

Условие

Требуется реализовать структуру данных, которая представляет из себя динамический массив, поддерживающий следующие операции:

• Присвоить числу, которое стоит на позиции u, значение p.
• Вставить число p после позиции u (но перед позицией u + 1, если она существует).
• Сообщить, сколько чисел, не превосходящих p, стоит на позициях с u по v включительно.

Элементы массива нумеруются с единицы.

Формат входного файла

В первой строке находятся два натуральных числа n и m — начальное количество элементов в массиве и количество операций (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 200 000). Во второй строке находится n целых чисел a₁, a₂, …, a_n  — элементы исходного массива (0 ≤ a_i ≤ 10⁶). Следующие m строк содержат описания операций в формате "1 u p" (u ≥ 1, u не превосходит текущего размера массива, 0 ≤ p ≤ 10⁶), "2 u p" (u ≥ 0, u не превосходит текущего размера массива, 0 ≤ p ≤ 10⁶) или "3 u v p" (1 ≤ u ≤ v, v не превосходит текущего размера массива, 0 ≤ p ≤ 10⁶).

Формат выходного файла

В выходном файле должны находиться ответы на запросы  — по одному в строке.

Примеры тестов

5 5
1 3 5 4 2
3 2 4 4
1 3 3
3 2 4 4
2 2 10
3 2 4 4

2
3
2