Скриня Пандори#9065

Скриня Пандори

1 секунда

128 мегабайтів

Легка

Щоб перемогти бога війни Арея, Кратос повинен дістатися до Скрині Пандори, яка наділяє свого власника по-справжньому божественною силою. Однак шлях до цього могутнього артефакту лежить через Храм Пандори, схований у глибинах древньої ущелини. На шляху до храму Кратосу доведеться подолати $n$ гір, причому висота $i$ -ї гори дорівнює $a_{i}$ a_i метрів.

Є тільки одна річ у цьому світі, якої боїться навіть могутній Кратос, — це висота. Він ніколи не стрибає вниз: різкі перепади лякають спартанця. Однак у нього є божественний дар — він може за одну дію зрівняти висоту всіх гір на відрізку з $i$ по $j$ , якщо $a_{i} = a_{j}$ a_i = a_j. Після застосування цієї сили всі гори від $i$ до $j$ (включно) стають висотою $a_{i}$ a_i.

Щоб дістатися до Храму Пандори, Кратосу необхідно використовувати свій дар так, щоб на всьому шляху висота не спадала, тобто виконувалась би умова: $a_{i} \leq a_{i + 1}$ a_i \le a_{i+1} для всіх $i = 1, 2, ..., n - 1$ i = 1, 2, ..., n - 1.

Кратос поспішає і не бажає привертати увагу Арея, тому він повинен звести кількість застосувань своєї сили до мінімуму. Допоможіть спартанцю дістатися до мети, виконавши мінімально можливу кількість зрівнянь.

Вхідні дані

У першому рядку задано число гір $n (1 \leq n \leq 1 0^{6})$ n~(1 \le n \le 10^6) на шляху до храму.

У другому рядку записано $n$ цілих чисел $a_{i} (1 \leq a_{i} \leq 1 0^{6})$ a_i~(1 \le a_i \le 10^6) — висоти гір.

Вихідні дані

У першому рядку виведіть мінімальну кількість дій $p$ , яку потрібно здійснити Кратосу, щоб шлях до храму став неспадним.

Потім у $p$ рядках виведіть по два числа — межі відрізка $l$ і $r (1 \leq l \leq r \leq n)$ r~(1 \le l \le r \le n), які Кратос повинен зрівняти.

Дії необхідно виводити в тому порядку, в якому Кратос повинен їх виконувати.

Якщо розв'язку не існує, виведіть $- 1$ .

Приклади

Приклад 1

Приклад 2