Поликарп — начинающий программист. Сейчас он исследует программу своего друга. Он уже обнаружил там функцию rangeIncrement(l, r), которая прибавляет единицу к каждому элементу некоторого массива a для всех индексов на отрезке [l, r]. Иными словами, эта функция делает следующее:
function rangeIncrement(l, r)
for i := l .. r do
a[i] = a[i] + 1
Поликарпу известно состояние массива a после серии вызовов этой функции. Он хочет определить минимальное количество вызовов функции, которые приведут к такому результату. Кроме того, он хочет понять какие именно вызовы функции нужны в таком случае. Гарантируется, что искомое количество вызовов не превосходит 105.
До вызовов функции rangeIncrement(l, r) все элементы массива равны нулям.
Выходные данные
В первую строку выведите t — наименьшее количество вызовов функции rangeIncrement(l, r), которые приведут к массиву из входных данных. Гарантируется, что это число окажется не более 105.
Далее выведите t строк — описания вызовов функции по одному в строке. Каждая строка должна содержать два целых числа li, ri (1 ≤ li ≤ ri ≤ n) — аргументы i-го вызова rangeIncrement(l, r). Вызовы функции могут быть осуществлены в любом порядке.
Если решений несколько, разрешается вывести любое.
Примечание
В первом примере требуется вызов для всего массива и четыре дополнительных вызова:
- один для отрезка [2,2] (т.е. второго элемента массива),
- три для отрезка [5,5] (т.е. пятого элемента массива).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2 1 1 4 1
|
5
2 2
5 5
5 5
5 5
1 6
|
|
2
|
5
1 0 1 0 1
|
3
1 1
3 3
5 5
|