Подумайте, как в этой задаче можно применить стек?

Вспомните решение через динамическое программирование за $$$O(nk)$$$.

Рассмотрите переходы в динамике

Подумайте как быстро совершать переход в динамике, чтобы получить решение за $$$O(n \log{k})$$$.

Вспомните задачу A. Подумайте как можно прикрутить сюда стек и находить минимум на отрезке за $$$O(1)$$$.

Рассмотрите $$$f(l, r) = \sum\limits_{l \le i \le r} a_i \cdot b_i$$$ на каком-то примере, выпишите первых пару слагаемых.

У вас переполнение :) используйте (__int128).

Как много раз значение $$$a_i \cdot b_i$$$ встретится в ответе? Оно встретится $$$i \cdot (n−i+1)$$$ раз.

Окей, теперь мы можем заметить, что для каждой позиции $$$i$$$ у нас есть значение $$$a_i \cdot b_i \cdot i \cdot (n−i+1)$$$ . Единственное переменное значение здесь — это $$$b_i$$$ . Пусть $$$val_i=a_i \cdot i \cdot (n−i+1)$$$ . \Заметьте, что вы не можете брать это значение по модулю 998244353 здесь, потому что тогда вы не сможете сравнивать эти значения правильно

Остается отсортировать массив $$$b$$$ и $$$val$$$ с собственным компаратором)

Вспомните бинарный поиск по ответу.

Это графовая задача.

Рассмотрите $$$dp[v, i]$$$ = предок вершины $$$v$$$ на расстоянии $$$2^i$$$.

$$$dp[v, 0]$$$ = предок. И $$$dp[v, j] = dp[ dp[v, j-1], j-1]$$$

Подумайте как при помощи этого массива дойти до любого предка вершины $$$k$$$.

К какому числу нужно сводить весь массив?

Как тут можно написать $$$dp$$$?

Используйте $$$dp[d]$$$ = минимальное число операций, чтобы получить один элемент со значением $d$.

Подумайте, можно ли посчитать количество единиц сразу для всех чисел, рассматривая не каждое число отдельно, а по разрядам.

Зафиксируйте некоторую битовую позицию $$$i$$$ (нумерация с нуля — младший бит $$$i=0$$$ и определите, как часто на этой позиции стоит $$$1$$$ в последовательности от $$$0$$$ до $$$n$$$.
Вспомните, что биты на позиции $$$i$$$ меняются по циклу длины $$$2^{i+1}$$$: сначала $$$2^i$$$ раз идут нули, потом $$$2^i$$$ раз — единицы, и так далее.

Подумайте, какой жадный алгоритм сюда можно прикрутить.

К какой сумме элементов множества $$$C$$$ и $$$B$$$ мы должны сводить.

Вспомните задачу о рюкзаке.

Вспомните задачу А, подумайте как это техника может вам помочь.

Попробуйте отсортировать массив из пар $$$(a[i], i)$$$ и написать $$$dp$$$ за $$$O(n^2)$$$.

Подумайте, как можно оптимизировать переход в $$$dp$$$, чтобы получить $$$O(n \cdot \log{n})$$$ или $$$O(n)$$$.

Оцените ограничение на $$$n$$$. Подумайте, как можно написать dp.

Используйте $$$dp[mask]$$$, где mask — битовая маска.

Попробуйте просто промоделировать процесс.

Подумайте, какую структуру данных можно использовать, чтобы отвечать на запрос за $$$O(\log{n})$$$.

Используйте дерево отрезков с массовыми операциями.

Отталкивайтесь от человека с максимальным $$$a_i$$$.

Добавим в начало массива $$$a$$$ элемент $$$0$$$, тогда длина ПНВП увеличится на единицу и всегда будет начинаться с $$$0$$$. Рассмотрим любую «почти-возрастающую» подпоследовательность и подчеркнём в ней те элементы, которые являются минимумами хотя бы в одной смежном паре. Например, в последовательности $$$[0, 1, 2, 7, 2, 2, 3]$$$ подчёркнутыми будут элементы $$$[0, 1, 2, 3]$$$. Что можно сказать про них?

Обратите внимание: подчеркнутые элементы образуют строго возрастающую подпоследовательность (IS), и между любыми двумя соседними подчеркнутыми элементами исходной ПНВП находится не более одного элемента. Какие ограничения накладываются на эти элементы?

Очевидно, что $$$a[pos_{i-1}] ≤ a[pos_i] ≥ a[pos_{i+1}]$$$, но для нашей задачи можно ослабить это до $$$a[pos_{i-1}] ≤ a[pos_i]$$$, поскольку условие «почти-возрастающей» всё ещё выполняется даже если $$$a[pos_i] \lt a[pos_{i+1}]$$$. Теперь заметим, что между $$$pos_{i-1}$$$ и $$$pos_{i+1}$$$ можно выбрать любое $$$j$$$ такое, что $$$a[pos_{i-1}] ≤ a[j]$$$.

Достаточно всегда брать первый такой $$$j$$$. Причём для каждого $$$i$$$ мы можем заранее вычислить $$$nxt_i = \min\limits_{j\le i}\bigl(a[j] \gt a[i] \bigr)$$$. Далее отметим, что каждый элемент $$$a[i]$$$ либо является «минимумом» в некоторой ПНВП, либо индекс $$$i$$$ равен $$$nxt_j$$$ для какого‑то другого $$$j$$$. Построим динамику $$$d[i]$$$ = длина ПНВП, заканчивающейся на элементе $$$a[i]$$$, причём $$$a[i]$$$ в этой подпоследовательности — последний «минимум».

Чтобы вычислить $$$d[i]$$$, будем перебирать $$$i$$$ слева направо и поддерживать в структуре «Дерево отрезков» (ST) для каждого возможного значения $$$x$$$ максимальную длину ПНВП, чьим последним «минимумом» является $$$x$$$. Тогда $$$d[i] = 1 + $$$(максимум вST на отрезке $$$[0, a[i]]$$$)

После вычисления $$$d_i$$$ выполняем два обновления в дереве отрезков: — в позиции $$$a_i$$$ присваиваем значение $$$d_i$$$; — при достижении индекса $$$\mathrm{nxt}_i$$$ снова в позиции $$$a_i$$$ кладём $$$d_i + 1$$$. После обработки всех $$$i$$$ в каждой ячейке $$$x$$$ дерева хранится длина максимальной ПНВП с последним «минимумом» $$$x$$$.
Тогда искомый ответ даётся выражением

Насколько далеко может уйти элемент вправо, за 1 раунд сортировки?

Для решения достаточно факта 1.

Насколько далеко может уйти элемент вправо, за $$$k$$$ раундов сортировки?

Самый маленький элемент массива лежит в $$$[a_0, a_1,..., a_k]$$$. Подумайте как можно применить кучу $$$(a_i, i)$$$.

Решив задачу для отрезка $$$[0...k-1]$$$ решите аналогичную для $$$[1...k+1]$$$.

Рассмотрите факторизацию каждого числа.

Если каждый множитель входит $$$k \cdot n$$$ раз, где $$$k$$$ — натуральное положительное число, то можно уравнять все числа в массиве: будем последовательно применять операцию так, чтобы каждое число состояло из одинакового набора простых множителей.