eolymp
bolt
Try our new interface for solving problems
Problems

Динамический массив

Динамический массив

Time limit 15 seconds
Memory limit 256 MiB

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

  1. Присвоить числу, которое стоит на позиции u, значение p.

  2. Вставить число p после позиции u (но перед позицией u+1, если она существует).

  3. Сообщить, сколько чисел, не превосходящих p, стоит на позициях с u по v включительно.

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

Input data

В первой строке находятся два натуральных числа n и m - начальное количество элементов в массиве и количество операций (1n200000, 1m200000). Во второй строке находится n целых чисел a_1, a_2, ..., a_n - элементы исходного массива (0a_i10^6). Следующие m строк содержат описания операций в формате

1 u p (u1, u не превосходит текущего размера массива, 0p10^6),

2 u p (u0, u не превосходит текущего размера массива, 0p10^6)

или

3 u v p (1uv, v не превосходит текущего размера массива, 0p10^6).

Output data

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

Examples

Input example #1
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
Output example #1
2
3
2
Author Сергей Копелиович