Пейте воду.
— Сунь-Цзы, Искусство стать здоровым программистом
Это сложная версия задачи. Единственное отличие в том, что в этой версии \(x=1\). Вы можете делать взломы только в том случае, если обе версии задачи решены.
Вам даны два целых числа \(n\) и \(x\) (\(x=1\)). В ряд выстроены \(n\) шаров, пронумерованных от \(1\) до \(n\) слева направо. Изначально на \(i\)-м шаре записано значение \(a_i\).
Для каждого целого числа \(i\) от \(1\) до \(n\) мы определяем функцию \(f(i)\) следующим образом:
- Предположим, что у вас есть множество \(S = \{1, 2, \ldots, i\}\).
- В рамках одной операции вам нужно выбрать целое число \(l\) (\(1 \leq l < i\)) из \(S\) такое, что \(l\) не является наибольшим элементом \(S\). Предположим, что \(r\) — наименьший элемент \(S\), значение которого больше \(l\).
- Если \(a_l > a_r\), то установить \(a_l = a_l + a_r\) и удалить \(r\) из \(S\).
- Если \(a_l < a_r\), то установить \(a_r = a_l + a_r\) и удалить \(l\) из \(S\).
- Если \(a_l = a_r\), вы выбираете целое число \(l\) или \(r\) для удаления из \(S\):
- Если вы решили удалить \(l\) из \(S\), вы устанавливаете \(a_r = a_l + a_r\) и удаляете \(l\) из \(S\).
- Если вы решили удалить \(r\) из \(S\), вы устанавливаете \(a_l = a_l + a_r\) и удаляете \(r\) из \(S\).
- \(f(i)\) обозначает количество целых чисел \(j\) (\(1 \le j \le i\)) таких, что можно получить \(S = \{j\}\), выполнив вышеописанную операцию ровно \(i - 1\) раз.
Для каждого целого числа \(i\) от \(x\) до \(n\) необходимо найти \(f(i)\).
Выходные данные
Для каждого набора входных данных выведите на отдельной строке \(n-x+1\) целых числа, разделенных пробелом, где \(j\)-е целое число равняется \(f(x+j-1)\).
Примечание
Для первого набора входных данных ниже приведены возможные значения \(j\) для каждого \(f(i)\) от \(1\) до \(n\).
- Для \(f(1)\) единственным возможным значением \(j\) является \(1\).
- Для \(f(2)\) единственным возможным значением \(j\) является \(2\).
- Для \(f(3)\) возможные значения \(j\): \(2\) и \(3\).
- Для \(f(4)\) возможные значения \(j\): \(2\) и \(3\).
- Для \(f(5)\) возможные значения \(j\): \(2\), \(3\) и \(4\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 1
1 2 3 2 1
7 1
4 5 1 2 1 4 5
11 1
1 2 3 1 1 9 3 2 4 1 3
|
1 1 2 2 3
1 1 1 1 1 3 4
1 1 2 2 2 1 1 1 3 3 4
|