Вам дан массив \(a\) из \(n\) целых положительных чисел и счет. Если ваш счет больше или равен \(a_i\), то вы можете увеличить свой счет на \(a_i\) и удалить \(a_i\) из массива.
Для каждого индекса \(i\) выведите максимальное количество дополнительных элементов массива, которые вы можете удалить, если удалите \(a_i\) и начнёте со счетом, равным \(a_i\). Обратите внимание, что удаление \(a_i\) не должно учитываться в ответе.
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел, \(i\)-е из которых обозначает максимальное количество дополнительных элементов массива, которые можно удалить, если удалить из массива \(a_i\) и начать со счетом \(a_i\).
Примечание
В первом наборе входных данных ответы выглядят следующим образом:
Если мы начинаем с \(i=4\), то наш изначальный счет равен \(a_4=4\) и \(a=[20,5,1,2]\). Мы можем удалить \(3\) дополнительных элемента в следующем порядке:
- Поскольку \(4 \ge 1\), мы можем удалить \(1\), и наш счет станет равен \(5\). После этого \(a=[20,5,2]\).
- Поскольку \(5 \ge 5\), мы можем удалить \(5\) и наш счет станет \(10\). После этого \(a=[20,2]\).
- Поскольку \(10 \ge 2\), мы можем удалить \(2\), и наш счет станет \(12\). После этого \(a=[20]\).
Если мы начнем с \(i=1\), то сможем удалить все оставшиеся элементы массива, поэтому ответ будет \(4\).
Если мы начнем с \(i=2\), то сможем удалить \(3\) дополнительных элемента в следующем порядке: \(1\), \(4\), \(2\).
Если мы начнем с \(i=3\), то не сможем удалить ни одного дополнительного элемента.
Если мы начинаем с \(i=5\), то можем удалить \(1\) дополнительный элемент: \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000
|
4 3 0 3 1
1 0 2
0
4 4 4 4 4
|