Jumps
Contest: Educational Codeforces Round 99 (Rated for Div. 2)
Difficulty rating: 1200
Tags: constructive algorithms, math

You are standing on the $$$\mathit{OX}$$$-axis at point $$$0$$$ and you want to move to an integer point $$$x > 0$$$.

You can make several jumps. Suppose you're currently at point $$$y$$$ ($$$y$$$ may be negative) and jump for the $$$k$$$-th time. You can:

- either jump to the point $$$y + k$$$
- or jump to the point $$$y - 1$$$.

What is the minimum number of jumps you need to reach the point $$$x$$$?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

The first and only line of each test case contains the single integer $$$x$$$ ($$$1 \le x \le 10^6$$$) — the destination point.

Output format:
For each test case, print the single integer — the minimum number of jumps to reach $$$x$$$. It can be proved that we can reach any integer point $$$x$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case $$$x = 1$$$, so you need only one jump: the $$$1$$$-st jump from $$$0$$$ to $$$0 + 1 = 1$$$.

In the second test case $$$x = 2$$$. You need at least three jumps:

- the $$$1$$$-st jump from $$$0$$$ to $$$0 + 1 = 1$$$;
- the $$$2$$$-nd jump from $$$1$$$ to $$$1 + 2 = 3$$$;
- the $$$3$$$-rd jump from $$$3$$$ to $$$3 - 1 = 2$$$;

Two jumps are not enough because these are the only possible variants:

- the $$$1$$$-st jump as $$$-1$$$ and the $$$2$$$-nd one as $$$-1$$$ — you'll reach $$$0 -1 -1 =-2$$$;
- the $$$1$$$-st jump as $$$-1$$$ and the $$$2$$$-nd one as $$$+2$$$ — you'll reach $$$0 -1 +2 = 1$$$;
- the $$$1$$$-st jump as $$$+1$$$ and the $$$2$$$-nd one as $$$-1$$$ — you'll reach $$$0 +1 -1 = 0$$$;
- the $$$1$$$-st jump as $$$+1$$$ and the $$$2$$$-nd one as $$$+2$$$ — you'll reach $$$0 +1 +2 = 3$$$;

In the third test case, you need two jumps: the $$$1$$$-st one as $$$+1$$$ and the $$$2$$$-nd one as $$$+2$$$, so $$$0 + 1 + 2 = 3$$$.

In the fourth test case, you need three jumps: the $$$1$$$-st one as $$$-1$$$, the $$$2$$$-nd one as $$$+2$$$ and the $$$3$$$-rd one as $$$+3$$$, so $$$0 - 1 + 2 + 3 = 4$$$.

Example input:
5
1
2
3
4
5

Example output:
1
3
2
3
4

Editorial:
At first, let's jump with $$$+k$$$ while $$$x$$$ is still greater than the current position. Now we finished in some position $$$pos = 1 + 2 + \dots + steps = \frac{steps (steps + 1)}{2} \ge x$$$. Note that $$$0 \le pos - x < steps$$$ otherwise, we wouldn't make the last step.
If $$$pos = x$$$ then we are lucky to finish right in point $$$x$$$. Otherwise, let's look at what happens if we replace one $$$+k$$$ with $$$-1$$$. Basically, we'll finish in $$$pos' = pos - (k + 1)$$$. And since $$$k \in [1, steps]$$$ then $$$pos' \in [pos - steps - 1, pos - 2]$$$.
We know that $$$pos - step < x$$$ so if $$$x < pos - 1$$$ then we can choose the corresponding $$$k = pos - x - 1$$$ and replace $$$+k$$$ with $$$-1$$$ and get straight to the point $$$x$$$. But if $$$x + 1 = pos$$$ then we need one extra operation $$$-1$$$.
To calculate $$$steps$$$ fast we can note we need at least $$$steps = \sqrt{2 \cdot x} - 1$$$ since $$$steps (steps + 1) \le (steps + 1)^2 \le 2x$$$ and then we can increase $$$steps$$$ while $$$steps (steps + 1) < 2x$$$.