Это сложная версия этой задачи. Различия между версиями заключаются в ограничении на \(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, 3, 8, 7, 6, 2, 1, 5]\). В этом случае мы можем задать \([k_1, k_2, k_3] = [2, 2, 7]\).
В пятом и шестом наборе можно доказать, что интересной перестановки не существует.
В седьмом наборе интересная перестановка с максимальным количеством инверсий это \([4, 7, 6, 3, 2, 1, 5]\). В этом случае мы можем задать \([k_1, k_2, k_3, k_4] = [1, 6, 1, 6]\).
В восьмом наборе интересная перестановка с максимальным количеством инверсий это \([4, 7, 3, 6, 2, 5, 1]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
2 0
2 1
1 2
5 1
2 4
8 3
1 4
2 5
7 8
7 2
1 4
4 7
7 3
1 2
1 7
3 7
7 4
1 3
4 7
1 3
4 7
7 3
1 2
3 4
5 6
|
1
0
8
18
-1
-1
15
15
|