Задача №112520. Барьер
Сегодняшние биологи изучают свойства биопоследовательностей. Биопоследовательность "— это последовательность из M элементов, которая
- содержит все целые числа от 0 до M - 1 ,
- начинается с 0 и заканчивается на M - 1 ,
- не содержит соседних элементов E и E + 1 , идущих в таком порядке.
Отрезок биопоследовательности называется непрерывным , если он содержит все целые числа в промежутке от значения первого элемента, который является минимальным на данном отрезке, до значения последнего элемента, который является максимальным на данном отрезке. Непрерывный отрезок называется барьером , если он не содержит более коротких непрерывных отрезков.
К примеру, рассмотрим биопоследовательность (0, 3, 5, 4, 6, 2, 1, 7) . Вся последовательность является непрерывным отрезком. Тем не менее, она содержит другой непрерывный отрезок (3, 5, 4, 6) и поэтому не является барьером. Непрерывный отрезок (3, 5, 4, 6) не содержит более коротких непрерывных отрезков, то есть является барьером. Более того, данная биопоследовательность содержит ровно один барьер.
Напишите программу, которая по данной биопоследовательности находит все её барьеры.
Первая строка ввода содержит единственное число M "— длину данной биопоследовательности ( 1 ≤ M ≤ 2 000 000 ). Следующие M строк содержат элементы биопоследовательности. В каждой строке содержится ровно одно число.
Решения, работающие только для M ≤ 5000 , будут оцениваться из 25 баллов. Решения, работающие только для M ≤ 60 000 , будут оцениваться из 50 баллов.
Первая строка вывода должна содержать единственное число H "— количество барьеров в заданной биопоследовательности. Следующие H строк должны описывать все барьеры данной биопоследовательности в порядке появления их начальных точек в биопоследовательности. Каждая из этих строк должна содержать два целых числа A и B (именно в таком порядке), разделённых пробелом, где элемент с номером A в заданной биопоследовательности "— это начало соответствующего барьера, а элемент с номером B "— конец этого барьера.
8 0 3 5 4 6 2 1 7
1 2 5