Ice Cream Balls
Contest: Codeforces Round 894 (Div. 3)
Difficulty rating: 1300
Tags: binary search, combinatorics, constructive algorithms, math

Tema decided to improve his ice cream making skills. He has already learned how to make ice cream in a cone using exactly two balls.

Before his ice cream obsession, Tema was interested in mathematics. Therefore, he is curious about the minimum number of balls he needs to have in order to make exactly $$$n$$$ different types of ice cream.

There are plenty possible ice cream flavours: $$$1, 2, 3, \dots$$$. Tema can make two-balls ice cream with any flavours (probably the same).

Two ice creams are considered different if their sets of ball flavours are different. For example, $$$\{1, 2\} = \{2, 1\}$$$, but $$$\{1, 1\} \neq \{1, 2\}$$$.

For example, having the following ice cream balls: $$$\{1, 1, 2\}$$$, Tema can make only two types of ice cream: $$$\{1, 1\}$$$ and $$$\{1, 2\}$$$.

Note, that Tema do not need to make all the ice cream cones at the same time. This means that he making ice cream cones independently. Also in order to make a following cone $$$\{x, x\}$$$ for some $$$x$$$, Tema needs at least $$$2$$$ balls of type $$$x$$$.

Help Tema answer this question. It can be shown that answer always exist.

Input format:
Each test consists of multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{18}$$$) — the number of ice cream types that Tema wants to make.

Output format:
For each test case, output a single integer — the minimum number of balls Tema needs to buy.

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

Note:
In the first sample, it is enough to have following balls types: $$$\{1, 1\}$$$. Note, that set $$$\{1\}$$$ if not enough since we need at least $$$2$$$ balls of a type $$$1$$$ in order to make such cone $$$\{1, 1\}$$$.

In the second sample, it is not possible to make it with $$$2$$$ balls, but it can be done with these balls: $$$\{1, 2, 3\}$$$.

In the third sample, $$$\{1, 2, 3, 4\}$$$ is optimal answer, so we can get following ice cream cones: $$$\{1, 2\}$$$, $$$\{1, 3\}$$$, $$$\{1, 4\}$$$, $$$\{2, 3\}$$$, $$$\{2, 4\}$$$, $$$\{3, 4\}$$$.

Example input:
5
1
3
6
179
1000000000000000000

Example output:
2
3
4
27
2648956421

Editorial:
First, let's note that having more than two balls of the same type is meaningless.
Let's denote $$$x$$$ as the number of flavours of balls represented by two instances of each ball. Let $$$y$$$ denote the number of flavours represented by a single instance.
Let's calculate the number of different ways to make an ice cream from these balls: we can make $$$x$$$ ice creams from balls of the same flavour and $$$\dfrac{(x + y) \cdot (x + y - 1)}{2}$$$ ice creams from balls of different flavours. In the problem, we are asked to select balls in such a way that $$$x + \dfrac{(x + y) \cdot (x + y - 1)}{2} = n$$$.
Note that for a fixed sum of $$$x + y$$$, we can uniquely determine $$$x$$$ and therefore $$$y$$$ (or determine that there is no solution for that sum).
Let's assume we have found an answer with a minimum sum of $$$x + y = k$$$. This means $$$\dfrac{k \cdot (k - 1)}{2} \leq n \leq \dfrac{k \cdot (k - 1)}{2} + k$$$. Moreover, if we find an answer with a sum of $$$x + y = k + 1$$$, then $$$k + \dfrac{k \cdot (k - 1)}{2} \leq n \leq k + \dfrac{k \cdot (k - 1)}{2} + k + 1$$$. From this, we can see that this is only possible when $$$n = k + \dfrac{k \cdot (k - 1)}{2}$$$. It is also evident that there are no answers with a sum greater than $$$k + 2$$$.
Now, all we need to do is perform a binary search on the sum of $$$x + y$$$ and then determine $$$x$$$ and $$$y$$$. And don't forget to consider the case when two sums of $$$x + y$$$ may be suitable, in order to choose the one with the fewest number of balls.