Динамічний масив#5311
Потрібно реалізувати структуру даних, яка являє собою динамічний масив, який підтримує наступні операції:
Присвоїти числу, яке стоїть на позиції , значення .
Вставити число після позиції (але перед позицією u+1, якщо вона існує).
Повідомити, скільки чисел, які не перевищують , стоїть на позиціях з по включно.
Елементи масиву нумеруються з одиниці.
У першому рядку знаходяться два натуральних числа та - початкова кількість елементів у масиві та кількість операцій (1 \leq n \leq 200000, 1 \leq m \leq 200000). У другому рядку знаходиться цілих чисел a_1, a_2, ..., a_n - елементи початкового масиву (0 \leq a_i \leq 10^6). Наступні рядків містять описи операцій у форматі
1 u p (u \geq 1, не перевищує поточного розміру масиву, 0 \leq p \leq 10^6),
2 u p (u \geq 0, не перевищує поточного розміру масиву, 0 \leq p \leq 10^6)
або
3 u v p (1 \leq u \leq v, не перевищує поточного розміру масиву, 0 \leq p \leq 10^6).
У вихідному файлі повинні знаходитись відповіді на запити - по одній у рядку.
Приклад 1