На координатной прямой \(Ox\) заданы \(n\) отрезков \([l_1, r_1]\), \([l_2, r_2]\), ..., \([l_n, r_n]\). Отрезок \([l, r]\) покрывает все точки от \(l\) до \(r\) включительно, то есть такие \(x\), что \(l \le x \le r\).
Отрезки могут располагаться произвольным образом — вкладываться друг в друга, совпадать и т.п. Отрезки могут вырождаться в точку, то есть допустимо, что \(l_i=r_i\).
Объединением набора отрезков называется такой минимальный набор отрезков, который покрывает в точности тот же набор точек, что и заданный набор. Например:
- если \(n=3\) и отрезки имеют вид \([3, 6]\), \([100, 100]\), \([5, 8]\), то их объединение состоит из \(2\) отрезков: \([3, 8]\) и \([100, 100]\);
- если \(n=5\) и отрезки имеют вид \([1, 2]\), \([2, 3]\), \([4, 5]\), \([4, 6]\), \([6, 6]\) то их объединение состоит из \(2\) отрезков: \([1, 3]\) и \([4, 6]\).
Очевидно, что объединение — это набор непересекающихся отрезков.
Требуется удалить ровно один отрезок из заданных \(n\) таким образом, чтобы количество отрезков в объединении оставшихся \(n-1\) было наибольшим.
Например, если \(n=4\) и отрезки имеют вид \([1, 4]\), \([2, 3]\), \([3, 6]\), \([5, 7]\), то:
- если из набора удалить первый отрезок, то останутся отрезки \([2, 3]\), \([3, 6]\), \([5, 7]\), объединение которых состоит из \(1\) отрезка;
- если из набора удалить второй отрезок, то останутся отрезки \([1, 4]\), \([3, 6]\), \([5, 7]\), объединение которых состоит из \(1\) отрезка;
- если из набора удалить третий отрезок, то останутся отрезки \([1, 4]\), \([2, 3]\), \([5, 7]\), объединение которых состоит из \(2\) отрезков;
- если из набора удалить четвертый отрезок, то останутся отрезки \([1, 4]\), \([2, 3]\), \([3, 6]\), объединение которых состоит из \(1\) отрезка.
Таким образом, в примере выше надо обязательно удалять третий отрезок, чтобы получить ответ \(2\).
Напишите программу, которая найдет наибольшее количество отрезков, которые получатся в объединении \(n-1\) оставшегося, если можно удалить любой из заданных \(n\) отрезков.
Обратите внимание, что если в заданном наборе есть несколько одинаковых отрезков, то удалить вы всё-равно можете ровно один из них. То есть набор отрезков после удаления одного будет содержать ровно \(n-1\) отрезок.