Массив \(a_1, a_2, \ldots, a_m\) изначально заполнен нулями. Вам даны \(n\) попарно различных отрезков \(1 \le l_i \le r_i \le m\). Вы должны выбрать произвольное подмножество этих отрезков (в частности, можно выбрать пустое множество). После этого происходит следующее:
- Для каждого \(i = 1, 2, \ldots, n\), если отрезок \((l_i, r_i)\) выбран в подмножество, то для каждого индекса \(l_i \le j \le r_i\) вы увеличиваете \(a_j\) на \(1\) (то есть \(a_j\) заменяете на \(a_j + 1\)). Если отрезок \((l_i, r_i)\) не выбран, массив не изменяется.
- После этого (после обработки всех значений \(i = 1, 2, \ldots, n\)) вы считаете \(\max(a)\) как максимальное значение среди всех элементов \(a\). Аналогично, \(\min(a)\) считается как минимальное значение.
- Наконец, стоимость выбранного подмножества отрезков объявляется равной \(\max(a) - \min(a)\).
Найдите наибольшую стоимость по всем подмножествам данного множества отрезков.
Выходные данные
Для каждого набора входных данных выведите наибольшую стоимость среди всех подмножеств данного множества отрезков.
Примечание
В первом наборе входных данных доступен всего один отрезок. Если его не выбирать, то массив будет равен \(a = [0, 0, 0]\), стоимость такого (пустого) подмножества отрезков равна \(0\). Если же выбрать единственный доступный отрезок, то массив станет равен \(a = [0, 1, 0]\), и стоимость будет равна \(1 - 0 = 1\).
Во втором наборе входных данных можно выбрать все отрезки: массив в таком случае будет равен \(a = [0, 1, 2, 3, 2, 1, 0, 0]\). Стоимость будет равна \(3 - 0 = 3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 3
2 2
3 8
2 4
3 5
4 6
6 3
1 1
1 2
1 3
2 2
2 3
3 3
7 6
2 2
1 6
1 2
5 6
1 5
4 4
3 6
6 27
6 26
5 17
2 3
20 21
1 22
12 24
4 1000000000
2 999999999
3 1000000000
123456789 987654321
9274 123456789
|
1
3
2
3
4
4
|