e-olymp

Race

Бесси участвует в гонке длиной K ( 1K109) метров. Она начинает бежать со скоростью 0 метров в секунду. Каждую секунду она может увеличить свою скорость на 1 метр в секунду, оставить скорость неизменной или уменьшить скорость на 1 метр в секунду. Например, в первую секунду она может увеличить скорость на 1 метр в секунду и пробежать за эту секунду 1 метр, или оставить скорость - метров в секунду и пробежать 0 метров. Бесси не может сделать свою скорость меньше нуля. Бесси всегда бежит к финишу и хочет финишировать после целого количества секунд. Кроме того, она не хочет прибежать слишком быстро, поэтому на финише её скорость не может превысить X (1X105) метров в секунду. Бесси хочет узнать, как быстро она сможет закончить гонку для N (1N1000 ) различных величин X .

Входные данные:

Первая строка содержит два целых числа K и N. Каждая из следующих N строк содержит одно целое число X.

Выходные данные:

Выведите N строк, каждая из них должна содержать одно целое число - минимальное количество времени, которое требуется Бесси, чтобы пробежать K метров и финишировать со скоростью меньше либо равной X.

Объяснение первого примера

При X=1, оптимальное решение таково:

  • Увеличить скорость до 1 м/с, пробежать 1 м
  • Увеличить скорость до 2 м/с, пробежать 2 метра, в сумме - 3 метра
  • Сохранить скорость 2 м/с, пробежать в сумме 5 метров
  • Сохранить скорость 2 м/с, пробежать в сумме 7 метров
  • Сохранить скорость 2 м/с, пробежать в сумме 9 метров
  • Уменьшить скорость до 1 м/с пробежать в сумме 10 метров

При X=3, оптимальное решение таково:

  • Увеличить скорость до 1 м/с, пробежать 1 м
  • Увеличить скорость до 2 м/с, пробежать в сумме 3 метра
  • Увеличить скорость до 3 м/с, пробежать в сумме 6 метров
  • Сохранить скорость 3 м/с, пробежать в сумме 9 метров
  • Сохранить скорость 3 м/с, после преодоления 10-го метра скорость 3 м/с

Приведём неверное решение при X=3:

  • Увеличить скорость до 1 м/с, пробежать 1 м
  • Увеличить скорость до 2 м/с, пробежать в сумме 3 метра
  • Увеличить скорость до 3 м/с, пробежать в сумме 6 метров
  • увеличить скорость до 4 м/с, пробежать в сумме 10 метров

Неверно, потому что скорость на финише Бесси равна 4.

Time limit 1 second
Memory limit 64 MiB
Input example #1
10 5
1
2
3
4
5
Output example #1
6
5
5
4
4
Source Usaco 2019-2020 January Bronze contest