В ряд расположены \(n\) городов, пронумерованных от \(1\) до \(n\).
В городах строятся телебашни. У телебашни, расположенной в \(i\)-м городе, есть высота \(h_i\) и радиус вещания \(w_i\). Эта башня может вещает в городе \(j\), если и только если выполнены следующие условия:
- \(i \le j \le w_i\), и
- для всех \(k\) таких, что \(i < k \le j\), выполняется \(h_k < h_i\).
Другими словами, телебашня в городе
\(i\) вещает в городе
\(j\), если
\(j \ge i\),
\(j\) находится в радиусе вещания
\(i\)-й телебашни, и
\(i\)-я телебашня строго выше всех башен между городами
\(i\) и
\(j\) (включая город
\(j\)).
Изначально во всех городах \(i\) выполняется \(h_i = 0\) и \(w_i = i\).
Затем происходят \(q\) событий. \(i\)-е событие может быть одним из следующих:
- Город \(c_i\) реконструирует свою телебашню так, что она станет самой высокой среди всех телебашен, и при этом ее радиус вещания \(w_{c_i}\) станет равным \(g_i\).
- Пусть \(b_j\) равно количеству телебашен, вещающих в городе \(j\). Вам нужно вычислить сумму \(b_j\) по всем \(j\), удовлетворяющим \(l_i \le j \le r_i\).
Ваша задача — обрабатывать все события и вывести ответ на все запросы.
Выходные данные
Для каждого запроса выведите сумму \(b_j\) в данном отрезке.
Примечание
В первом примере единственная телебашня в городе \(1\) вещает в городе \(1\) до и после реконструкции.
Во втором примере после каждой реконструкции массив \(b\) выглядят следующим образом:
- \([1, 1, 1, 2, 1]\);
- \([1, 2, 2, 3, 2]\);
- \([1, 2, 2, 1, 2]\);
- \([1, 1, 2, 1, 2]\);
- \([1, 1, 2, 1, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 3
2 1 1
1 1 1
2 1 1
|
1
1
|
|
2
|
5 10
1 3 4
2 3 5
1 1 5
2 1 5
1 4 5
2 2 4
1 2 3
2 1 3
1 5 5
2 2 5
|
4
10
5
4
5
|