AquaMoon дала RiverHamster последовательность целых чисел \(a_1,a_2,\dots,a_n\), а RiverHamster задал вам \(q\) запросов. Каждый запрос характеризуется двумя целыми числами \(l\) и \(r\).
При ответе на каждый запрос вы можете выбрать любой непрерывный отрезок последовательности и вычесть из всех его элементов одно и то же неотрицательное число. Выполнять эту операцию можно несколько (возможно, ноль) раз. Однако нельзя выбрать два пересекающихся отрезка, которые были бы не вложены друг в друга. Ваша задача — превратить в \(0\) все числа, у которых изначальное значение лежало в диапазоне \([l, r]\). Сделать это нужно за наименьшее число операций.
Обратите внимание, что запросы независимы, числа в массиве возвращаются к своим первоначальным значениям между запросами.
Формально, для каждого запроса нужно найти наименьшее \(m\), для которого существует последовательность \(\{(x_j,y_j,z_j)\}_{j=1}^{m}\), удовлетворяющая следующим условиями:
- для любого \(1 \le j \leq m\) выполняется \(z_j \ge 0\) и \(1 \le x_j \le y_j \leq n\) (здесь \([x_j, y_j]\) представляют отрезки в последовательности);
- для любых \(1 \le j < k \le m\) выполняется \([x_j,y_j]\subseteq[x_{k},y_{k}]\), \([x_k,y_k]\subseteq[x_{j},y_{j}]\), или \([x_j,y_j]\cap[x_{k},y_{k}]=\varnothing\);
- для любого \(1 \le i \le n\), такого что \(l \le a_i \leq r\), выполняется \(\){\large a_i = \sum\limits_{\substack {1 \le j \le m \\ x_j \le i \le y_j}} z_j. }\(\)
Выходные данные
Выведите ответ на каждый запрос на отдельной строке.
Примечание
В первом наборе входных данных рассмотрим второй запрос: \(l = 2\), \(r = 2\). Элементы, которые нужно обнулить, суть \([a_3, a_5, a_{10}] = [2, 2, 2]\). Достаточно применить последовательность операций \(\{(2, 10, 2)\}\).
В четвёртом запросе \(l = 2\), \(r = 3\). Обнулить нужно элементы \([a_3, a_4, a_5, a_7, a_{10}] = [2, 3, 2, 3, 2]\). Достаточно применить последовательность операций \(\{(1, 10, 2), (4, 4, 1), (7, 7, 1)\}\).
Во втором наборе входных данных можно заметить, что последовательность операций \(\{(1, 2, 1), (2, 3, 2)\}\) не является допустимой, потому что два используемых отрезка пересекаются, но не вложены один в другой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 8
1 6 2 3 2 6 3 10 1 2
1 10
2 2
3 3
2 3
1 3
3 6
4 6
5 5
|
8
1
1
3
5
3
1
0
|
|
2
|
3 1
1 3 2
1 3
|
3
|