Полное решение:

У этой задачи есть 2 решения:

1. Простой брутфорс. Пусть x = префикс, y = середина, z = суффикс. При маленьких ограничениях на n можно написать кубический перебор. Поддерживаем l, r, где x = [1,l], y = [l+1,r], z = [r+1,n]. Перебираем все такие пары (l,r) и считаем суммы для x, y, z. Это решение работает за O(n³).

2. Конструктив. Заметим: сумма x+y+z при правильном разбиении должна делиться на 3. Возможные варианты: [1,1,1], [0,1,2], [1,0,2], [2,1,0]. То есть условие корректности: либо все три суммы равны, либо все попарно различны. Тогда можно просто взять x = [1,1], y = [2,n-1], z = [n,n]. В этом случае получится корректное разбиение. То есть выбираем l = 1, r = n-1. Если же sum(x,y,z) % 3 != 0, то правильного разбиения не существует, и нужно вывести 0 0. Иначе выводим найденное разбиение.

Идея: Нужно сделать как можно больше элементов «не на своём месте» по сравнению с отсортированным вариантом. Нули можно заменить на отсутствующие элементы так, чтобы они оказались максимально вне своих целевых индексов.

Подход:

1. Построить отсортированную версию массива (целевая позиция для каждого значения).
2. Собрать все отсутствующие в исходном элементы — кандидаты для подстановки в нули. Лучше брать наибольшие отсутствующие.
3. Заполнить нули этими значениями.
4. После замены задача сводится к поиску максимальной длины отрезка, в котором a[i] != target_pos_of(a[i]). Это решается двумя указателями: расширяем правый, пока условие выполняется, при нарушении сдвигаем левый.

Сложность: сортировка + два указателя → O(n log n).

Идея (динамика по позиции и состоянию swap): На каждом индексе можно либо сделать swap между a[i] и b[i], либо не делать. Включение индекса в хорошее множество зависит от соседних сравнений. Поэтому держим два состояния для позиции i:

dp[i][0] — количество способов (или достижимость), если на i не сделали swap. dp[i][1] — если на i сделали swap.

Переходы (условия): Чтобы перейти в dp[i][1], нужно, сравнив с i-1, чтобы условия после и перед swap'ов выполнялись: — если и на i-1 была swap: b[i-1] <= a[i] и a[i-1] <= b[i] — если на i-1 не было swap: a[i-1] <= a[i] и b[i-1] <= b[i] Аналогичные проверки для dp[i][0].

Таким образом на каждом i обновляем dp[i][0] и dp[i][1] суммируя допустимые переходы из i-1. Не забываем про модуль, если нужно считать числа способов.

Выведем наш ответ, как dp[n][0]+dp[n][1].

Сложность: O(n) по времени и O(1) по памяти (храним только предыдущий слой).

Идея: Если фиксировать d, итоговые значения группируются по диапазонам длины d: [1..d], [d+1..2d], ... Для каждого диапазона все числа переходят в одно значение (value_level).

Алгоритм:

1. Посчитать частоты каждого числа до mx = max(a).
2. Построить префикс частот pref, чтобы быстро получить количество элементов в любом числовом диапазоне [L..R] как pref[R] — pref[L-1].
3. Для каждого d от 1 до mx: — Итерируем по диапазонам длины d: [1..d], [d+1..2d], ... — Через pref получаем количество элементов cnt в каждом диапазоне. — Вычисляем вклад диапазона в итоговую сумму: cnt * value_level (value_level = (R)/d округлённо вверх или по нужной формуле). — Если есть лишние элементы, которые нельзя покрыть (d — cnt), учитываем штраф/уменьшение.
4. Для каждого d суммируем вклад по всем диапазонам и обновляем максимум.

Почему это быстро: суммарно для всех d работа примерно mx * (1 + 1/2 + 1/3 + ...) = mx * log(mx).

Сложность: ~ O(mx * log mx), где mx = max(a), с O(mx) памяти на частоты и префиксы.