Задача №111151. Монотонная последовательность
Вася с Петей играют в следующую игру. Вася берет n картонных карточек, и на каждой из них с обеих сторон пишет по числу. После этого он выкладывает карточки в некотором порядке перед Петей. Пронумеруем карточки от 1 до n в том порядке, в котором их выложил Вася. Петя пытается добиться того, чтобы последовательность чисел, написанных на карточках стала строго монотонной (возрастающей или убывающей). Для этого ему разрешается совершать следующие действия: выбрать два числа l и r, такие что 1 ≤ l ≤ r ≤ n и перевернуть каждую из карточек от карточки номер l до карточки номер r. Напомним, что последовательность c1, ..., cn называется строго возрастающей, если выполняются неравенства c1 < c2 < ... < cn, и строго убывающей, если выполняются неравенства c1 > c2 > ... > cn. Напишите программу, которая по описанию карточек определяет, какое минимальное число действий должен совершить Петя для того, чтобы добиться своей цели.
Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100 000). Каждая из последующих n строк описывает одну карточку и содержит два числа – ai написано на ее лицевой стороне, а bi — на оборотной. Все числа ai и bi находятся в диапазоне от 1 до 109.
В первой строке выходного файла выведите минимальное число действий, которое должен совершить Петя. Если Петина цель недостижима, то выведите в выходной файл число -1.
3
3 4
1 2
4 1
1
3
1 2
4 1
3 4
-1
6
1 2
3 2
2 3
4 5
6 5
5 6
2
Подзадача 1. N не превосходит 100. Решение оценивается в 30 баллов.
Подзадача 2. N не превосходит 1 000. Решение оценивается в 30 баллов.
Подзадача 3. Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов.