Ящик Пандори
Щоб перемогти бога війни Ареса, Кратос повинен дістатися до скриньки Пандори, яка наділяє свого власника справжньою божественною силою. На жаль, скринька захована в глибинах храму Пандори, а на шляху до храму розташовані n гір, де висота i-ї гори дорівнює a[i] метрам.
Єдина річ, якої боїться могутній Кратос, — це висота. Тому він ніколи не спускається і не стрибає вниз, адже великі перепади висот його лякають. Проте він має божественний навик: якщо висота i-ї гори дорівнює висоті j-ї, Кратос може за одну дію зробити всі гори на відрізку від i до j включно висотою a[i].
Щоб дістатися до храму Пандори, Кратосу потрібно застосувати свій чарівний навик до певних відрізків гір так, щоб йому ніколи не довелося спускатися вниз, тобто виконувалася б умова a[i] ≤ a[i+1].
Кратос дуже поспішає і не хоче бути поміченим Аресом, тому не може занадто часто змінювати висоти гір. Допоможіть Кратосу дістатися до храму Пандори за мінімальну кількість дій.
Вхідні дані
У першому рядку дано кількість гір n (1 ≤ n ≤ 10^6) на шляху до храму Пандори. У другому рядку дано n цілих чисел a[i] (1 ≤ a[i] ≤ 10^6) - висоти гір.
Вихідні дані
У першому рядку виведіть мінімальну кількість дій p, які потрібно здійснити Кратосу, щоб дістатися до храму Пандори. У кожному з наступних p рядків виведіть два числа l і r - межі чергового відрізка гір, з яким потрібно здійснити дію по вирівнюванню. Дії виводьте в тому порядку, в якому їх повинен здійснювати Кратос. Якщо розв'язку немає, в єдиному рядку виведіть "-1".