Страница: 1 Отображать по:
#1254
Монотонная последовательность
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Вася с Петей играют в следующую игру. Вася берет n картонных карточек, и на каждой из них с обеих сторон пишет по числу. После этого он выкладывает карточки в некотором порядке перед Петей. Пронумеруем карточки от 1 до n в том порядке, в котором их выложил Вася.

Петя пытается добиться того, чтобы последовательность чисел, написанных на карточках стала строго монотонной (возрастающей или убывающей). Для этого ему разрешается совершать следующие действия: выбрать два числа l и r, такие что 1 ≤ l≤ r ≤ n и перевернуть каждую из карточек от карточки номер l до карточки номер r.

Напомним, что последовательность c1, . . . , cn называется строго возрастающей, если выполняются неравенства c1 < c2 < … < cn, и строго убывающей, если выполняются неравенства c1 > c2 > … > cn.

Напишите программу, которая по описанию карточек определяет, какое минимальное число действий должен совершить Петя для того, чтобы добиться своей цели.

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

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100000). Каждая из последующих 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 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест