Единственная разница между простой и сложной версиями состоит в ограничениях на \(t\) и \(n\).
Вам задан массив \(a\), состоящий из \(n\) различных целых чисел \(a_1, a_2, \ldots, a_n\).
Определим стоимость массива \(p_1, p_2, \ldots p_k\) как минимальное количество времени, необходимое для сортировки этого массива с использованием произвольного количества операций сортировки диапазона. В каждой операции сортировки диапазона вы будете делать следующее:
- Выберите два целых числа \(l\) и \(r\) (\(1 \le l < r \le k\)).
- Отсортируйте подмассив \(p_l, p_{l + 1}, \ldots, p_r\) за \(r - l\) секунд.
Пожалуйста, посчитайте сумму стоимостей по всем подмассивам массива \(a\).
Подмассив массива определяется как непрерывная последовательность элементов массива.
Выходные данные
Для каждого набора входных данных выведите сумму стоимостей по всем подмассивам массива \(a\).
Примечание
В первом наборе входных данных:
- Подмассив \([6]\) уже отсортирован, поэтому его стоимость равна \(0\).
- Подмассив \([4]\) уже отсортирован, поэтому его стоимость равна \(0\).
- Подмассив \([6, 4]\) можно отсортировать за одну операцию, выбрав \(l = 1\) и \(r = 2\). Его стоимость равна \(1\).
Сумма стоимостей по всем подмассивам данного массива равна
\(0 + 0 + 1 = 1\).
Во втором наборе входных данных:
- Подмассив \([3]\) уже отсортирован, поэтому его стоимость равна \(0\).
- Подмассив \([10]\) уже отсортирован, поэтому его стоимость равна \(0\).
- Подмассив \([6]\) уже отсортирован, поэтому его стоимость равна \(0\).
- Подмассив \([3, 10]\) уже отсортирован, поэтому его стоимость равна \(0\).
- Подмассив \([10, 6]\) можно отсортировать за одну операцию, выбрав \(l = 1\) и \(r = 2\). Его стоимость равна \(2 - 1 = 1\).
- Подмассив \([3, 10, 6]\) можно отсортировать за одну операцию, выбрав \(l = 2\) и \(r = 3\). Его стоимость равна \(3 - 2 = 1\).
Сумма стоимостей по всем подмассивам данного массива равна
\(0 + 0 + 0 + 0 + 1 + 1 = 2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
|
1
2
8
16
232
|