Bessie’s Constrained Race

Bessie is participating in a running race of \(K\) meters (\(1 \le K \le 10^9\)). She starts at a speed of 0 m/s. At the beginning of each second, she may choose to either increase her speed by 1 m/s, keep her speed unchanged, or decrease her speed by 1 m/s (her speed can never drop below 0). For example, in the first second, she could decide to accelerate to 1 m/s and run 1 meter, or continue at 0 m/s and run 0 meters.

Since Bessie always runs toward the finish, she wants to complete the race in an integer number of seconds. However, she does not want to be running too fast at the finish line: when Bessie covers exactly \(K\) meters, she requires that her speed is at most \(X\) m/s (\(1 \le X \le 10^5\)).

Bessie would like to know the minimum time (in seconds) required to finish the race for \(N\) different values of \(X\) (\(1 \le N \le 1000\)).

Notes on the strategy:

During an optimal race, Bessie will accelerate as much as possible initially and then, if necessary, decelerate so that her final speed does not exceed \(X\). More precisely, if she reaches a maximum speed \(a\) during the race, she must decelerate for \(a - X\) seconds (if \(a > X\)). In the acceleration phase she covers \(\frac{a(a+1)}{2}\) meters and in the deceleration phase she covers \( \frac{(a-1+X)(a-X)}{2}\) meters. If there is any extra time, she can run at the maximum speed \(a\). Thus, if the total number of seconds is \(T\) and \(T > X\), an optimal strategy is to choose \[ a = \left\lfloor \frac{T+X}{2} \right\rfloor, \quad b = T - 2a + X. \] The total distance covered will then be \[ D = \frac{a(a+1)}{2} + a \cdot b + \frac{(a-1+X)(a-X)}{2}. \] If \(T \le X\), Bessie can simply accelerate every second and cover \(\frac{T(T+1)}{2}\) meters.

inputFormat

The first line contains two integers \(K\) and \(N\) representing the distance of the race and the number of queries, respectively.

Each of the next \(N\) lines contains one integer \(X\) specifying the maximum allowed finishing speed for that query.

K N
X_1
X_2
...
X_N

outputFormat

For each query, output the minimum number of seconds required for Bessie to finish the race under the given constraint. Each answer should be on its own line.

sample

9 2
1
2

5
4