Пейте воду.
— Сунь-Цзы, Искусство стать здоровым программистом
Это лёгкая версия задачи. Единственное отличие в том, что в этой версии \(x=n\). Вы можете делать взломы только в том случае, если обе версии задачи решены.
Вам даны два целых числа \(n\) и \(x\) (\(x=n\)). В ряд выстроены \(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)\).
Примечание
В первом наборе входных данных требуется вычислить \(f(5)\). Можно показать, что после \(4\) операций \(S\) может содержать \(2\), \(3\) или \(4\). Ниже показаны операции, необходимые для того, чтобы получить \(S = \{4\}\).
- Изначально \(S = \{1, 2, 3, 4, 5\}\) и \(a = [1, 2, 3, 2, 1]\).
- Выбираем \(l = 1\). Тогда \(r = 2\). Так как \(a_1 < a_2\), зададим \(a_2 = 1 + 2\) и удалим \(1\) из \(S\). Теперь \(S = \{2, 3, 4, 5\}\) и \(a = [1, 3, 3, 2, 1]\).
- Выбираем \(l = 4\). Тогда \(r = 5\). Поскольку \(a_4 > a_5\), зададим \(a_4 = 2 + 1\) и удалим \(5\) из \(S\). Теперь \(S = \{2, 3, 4\}\) и \(a = [1, 3, 3, 3, 1]\).
- Выбираем \(l = 3\). Тогда \(r = 4\). Поскольку \(a_3 = a_4\), у нас есть выбор, удалить \(3\) или \(4\). Поскольку мы хотим сохранить \(4\), удалим \(3\). Итак, зададим \(a_4 = 3 + 3\) и удалим \(3\) из \(S\). Теперь \(S = \{2, 4\}\) и \(a = [1, 3, 3, 6, 1]\).
- Выбираем \(l = 2\). Тогда \(r = 4\). Поскольку \(a_2 < a_4\), зададим \(a_4 = 3 + 6\) и удалим \(2\) из \(S\). Наконец, \(S = \{4\}\) и \(a = [1, 3, 3, 9, 1]\).
Во втором наборе входных данных требуется вычислить \(f(7)\). Можно показать, что после \(6\) операций \(S\) может содержать \(2\), \(4\), \(6\) или \(7\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 5
1 2 3 2 1
7 7
4 5 1 2 1 4 5
11 11
1 2 3 1 1 9 3 2 4 1 3
|
3
4
4
|