В ряд расположено \(100\) комнат и \(99\) дверей между ними, \(i\)-я дверь соединяет комнаты \(i\) и \(i+1\). Каждая дверь может быть открыта или закрыта. Изначально все двери открыты.
Скажем, что комната \(x\) достижима из комнаты \(y\), если все двери между ними открыты.
Вы знаете, что:
- Алиса находится в какой-то комнате из отрезка \([l, r]\);
- Боб находится в какой-то комнате из отрезка \([L, R]\);
- Алиса и Боб находятся в разных комнатах.
Однако вы не знаете, в каких именно комнатах они находятся.
Вы не хотите, чтобы Алиса и Боб могли добраться друг до друга, поэтому собираетесь закрыть некоторые двери, чтобы этого избежать. Какое минимальное количество дверей необходимо закрыть, чтобы Алиса и Боб не могли встретиться, независимо от их начальных позиций внутри заданных отрезков?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество дверей, которое необходимо закрыть, чтобы Алиса и Боб не могли встретиться, независимо от их начальных позиций внутри заданных отрезков.
Примечание
В первом наборе входных данных достаточно закрыть дверь между комнатами \(2\) и \(3\).
Во втором наборе входных данных нужно закрыть следующие двери: \((2,3)\), \((3,4)\), \((4,5)\).
В третьем наборе входных данных нужно закрыть следующие двери: \((5, 6)\) и \((6,7)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
3 4
2 5
2 5
3 7
6 7
4 5
2 8
|
1
3
2
3
|