Давайте назовем массив \(a\), состоящий из \(n\) положительных (больших, чем \(0\)) целых чисел, красивым, если для каждого \(i\) от \(1\) до \(n\) выполняется следующее условие: либо \(a_i = 1\), либо хотя бы одно из чисел \(a_i - 1\) и \(a_i - 2\) присутствует в массиве.
Например:
- массив \([5, 3, 1]\) — красивый: для \(a_1\) число \(a_1 - 2 = 3\) присутствует в массиве; для \(a_2\) число \(a_2 - 2 = 1\) присутствует в массиве; для \(a_3\) выполняется условие \(a_3 = 1\);
- массив \([1, 2, 2, 2, 2]\) — красивый: для \(a_1\) выполняется условие \(a_1 = 1\); для каждого из остальных \(a_i\) число \(a_i - 1 = 1\) присутствует в массиве;
- массив \([1, 4]\) — некрасивый: для \(a_2\) ни числа \(a_2 - 2 = 2\), ни числа \(a_2 - 1 = 3\) нет в массиве, и \(a_2 \ne 1\);
- массив \([2]\) — некрасивый: для \(a_1\) ни числа \(a_1 - 1 = 1\), ни числа \(a_1 - 2 = 0\) нет в массиве, и \(a_1 \ne 1\);
- массив \([2, 1, 3]\) — красивый: для \(a_1\) число \(a_1 - 1 = 1\) присутствует в массиве; для \(a_2\) выполняется условие \(a_2 = 1\); для \(a_3\) чисдл \(a_3 - 2 = 1\) присутствует в массиве.
Вам дано положительное целое число \(s\). Найдите минимально возможный размер красивого массива, сумма элементов которого равна \(s\).
Выходные данные
Выведите \(t\) целых чисел, \(i\)-е из них должно быть ответом на \(i\)-й набор входных данных (то есть должно быть равно минимально возможному размеру красивого массива с суммой элементов, равной \(s\)).
Примечание
Рассмотрим пример из условия:
- в первом наборе входных данных массив \([1]\) удовлетворяет всем условиям;
- во втором наборе входных данных массив \([3, 4, 1]\) удовлетворяет всем условиям;
- в третьем наборе входных данных массив \([1, 2, 4]\) удовлетворяет всем условиям;
- в четвертом наборе входных данных массив \([1, 4, 6, 8, 10, 2, 11]\) удовлетворяет всем условиям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
8
7
42
|
1
3
3
7
|