Поликарп решил устроить себе марафон решения задач. Он хочет решить \(s\) задач за \(n\) дней. Пусть \(a_i\) будет количеством задач, которые он решит в \(i\)-й день. Он хочет найти такое разбиение задач на дни, что:
- \(a_i\) — это целое число для всех \(i\) от \(1\) до \(n\);
- \(a_i \ge 1\) для всех \(i\) от \(1\) до \(n\);
- \(a_{i + 1} \ge a_i\) для всех \(i\) от \(1\) до \(n-1\);
- \(a_{i + 1} \le 2 \cdot a_i\) для всех \(i\) от \(1\) до \(n-1\);
- \(a_n\) как можно больше.
Обратите внимание, что \(a_1\) может быть произвольно большим.
Какое наибольшее значение \(a_n\) Поликарп может получить?
Выходные данные
На каждый набор входных данных выведите одно целое число — наибольшее значение \(a_n\).
Примечание
В первом наборе входных данных есть только одно разбиение: \([15]\).
Во втором примере разбиение, которое максимизирует \(a_n\): \([2, 3, 4]\).
В третьем примере разбиение, которое максимизирует \(a_n\): \([2, 4]\). \([3, 3]\) является корректным разбиением, но \(a_n=3\), что меньше \(4\). \([1, 5]\) не является корректным разбиением, потому что \(5 > 2 \cdot 1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 15
3 9
2 6
|
15
4
4
|