C. Увеличения на отрезке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп — начинающий программист. Сейчас он исследует программу своего друга. Он уже обнаружил там функцию 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) все элементы массива равны нулям.

Входные данные

В первой строке входных данных записано целое число n (1 ≤ n ≤ 105) — длина массива a[1... n].

Вторая строка содержит его целочисленные элементы, записанные через пробел, a[1], a[2], ..., a[n] (0 ≤ a[i] ≤ 105) после некоторой серии вызовов функции rangeIncrement(l, r).

Гарантируется, что хотя бы один элемент массива отличен от 0. Гарантируется, что ответ содержит не более 105 вызовов функции rangeIncrement(l, r).

Выходные данные

В первую строку выведите t — наименьшее количество вызовов функции rangeIncrement(l, r), которые приведут к массиву из входных данных. Гарантируется, что это число окажется не более 105.

Далее выведите t строк — описания вызовов функции по одному в строке. Каждая строка должна содержать два целых числа li, ri (1 ≤ li ≤ ri ≤ n) — аргументы i-го вызова rangeIncrement(l, r). Вызовы функции могут быть осуществлены в любом порядке.

Если решений несколько, разрешается вывести любое.

Примеры
Входные данные
6
1 2 1 1 4 1
Выходные данные
5
2 2
5 5
5 5
5 5
1 6
Входные данные
5
1 0 1 0 1
Выходные данные
3
1 1
3 3
5 5
Примечание

В первом примере требуется вызов для всего массива и четыре дополнительных вызова:

  • один для отрезка [2,2] (т.е. второго элемента массива),
  • три для отрезка [5,5] (т.е. пятого элемента массива).