Это легкая версия данной задачи. Различия между версиями заключаются в ограничении на \(m\) и в том, что \(r_i < l_{i + 1}\) выполняется для каждого \(i\) от \(1\) до \(m - 1\) в легкой версии. Вы можете взломы только в том случае, если обе версии задачи решены.
Черепаха дает вам \(m\) отрезков \([l_1, r_1], [l_2, r_2], \ldots, [l_m, r_m]\). Она считает, что перестановка \(p\) интересна, если существуют целые числа \(k_i\) для каждого отрезка (\(l_i \le k_i < r_i\)), такие что если она вычислит \(a_i = \max\limits_{j = l_i}^{k_i} p_j, b_i = \min\limits_{j = k_i + 1}^{r_i} p_j\) для каждого целого числа \(i\) от \(1\) до \(m\), то будет выполняться следующее условие:
\(\)\max\limits_{i = 1}^m a_i < \min\limits_{i = 1}^m b_i\(\)
Черепаха хочет, чтобы вы вычислили максимальное количество инверсий среди всех интересных перестановок длины \(n\), или сказали ей, если интересной перестановки не существует.
Инверсией перестановки \(p\) называется пара целых чисел \((i, j)\) (\(1 \le i < j \le n\)) такая, что \(p_i > p_j\).
Выходные данные
Для каждого набора входных данных, если интересной перестановки не существует, выведите единственное целое число \(-1\).
В противном случае выведите единственное целое число — максимальное количество инверсий.
Примечание
В третьем наборе входных данных интересная перестановка с максимальным количеством инверсий это \([5, 2, 4, 3, 1]\).
В четвертом наборе входных данных интересная перестановка с максимальным количеством инверсий это \([4, 8, 7, 6, 3, 2, 1, 5]\). В этом случае мы можем задать \([k_1, k_2] = [1, 7]\).
В пятом наборе входных данных интересная перестановка с максимальным количеством инверсий это \([4, 7, 6, 3, 2, 1, 5]\).
В шестом наборе входных данных интересная перестановка с максимальным количеством инверсий это \([4, 7, 3, 6, 2, 5, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 0
2 1
1 2
5 1
2 4
8 2
1 4
6 8
7 2
1 3
4 7
7 3
1 2
3 4
5 6
|
1
0
8
21
15
15
|