Paint a Strip
Contest: Codeforces Round 992 (Div. 2)
Difficulty rating: 1000
Tags: constructive algorithms, greedy, math

You have an array of zeros $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$.

You can perform two types of operations on it:

1. Choose an index $$$i$$$ such that $$$1 \le i \le n$$$ and $$$a_i = 0$$$, and assign $$$1$$$ to $$$a_i$$$;
2. Choose a pair of indices $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$, $$$a_l = 1$$$, $$$a_r = 1$$$, $$$a_l + \ldots + a_r \ge \lceil\frac{r - l + 1}{2}\rceil$$$, and assign $$$1$$$ to $$$a_i$$$ for all $$$l \le i \le r$$$.

What is the minimum number of operations of the first type needed to make all elements of the array equal to one?

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The only line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the array.

Note that there is no limit on the sum of $$$n$$$ over all test cases.

Output format:
For each test case, print one integer — the minimum number of needed operations of first type.

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

Note:
In the first test case, you can perform an operation of the $$$1$$$st type with $$$i = 1$$$.

In the second test case, you can perform the following sequence of operations:

1. Operation of $$$1$$$st type, $$$i = 1$$$. After performing this operation, the array will look like this: $$$[1, 0]$$$.
2. Operation of $$$1$$$st type, $$$i = 2$$$. After performing this operation, the array will look like this: $$$[1, 1]$$$.

The sequence of operations in the second test case

In the third test case, you can perform the following sequence of operations:

1. Operation of $$$1$$$st type, $$$i = 1$$$. After performing this operation, the array will look like this: $$$[1, 0, 0, 0]$$$.
2. Operation of $$$1$$$st type, $$$i = 4$$$. After performing this operation, the array will look like this: $$$[1, 0, 0, 1]$$$.
3. Operation of $$$2$$$nd type, $$$l = 1$$$, $$$r = 4$$$. On this segment, $$$a_l + \ldots + a_r = a_1 + a_2 + a_3 + a_4 = 2$$$, which is not less than $$$\lceil\frac{r - l + 1}{2}\rceil = 2$$$. After performing this operation, the array will look like this: $$$[1, 1, 1, 1]$$$.

The sequence of operations in the third test case

Example input:
4
1
2
4
20

Example output:
1
2
2
4

Editorial:
At each moment of time, the array contains a number of non-intersecting segments consisting only of ones. Using an operation of the first type can increase the number of these segments by $$$1$$$. Using an operation of the second type decreases the number of these segments by $$$x - 1$$$, where $$$x$$$ — is the number of segments that this operation covers. Therefore, the number of operations of the second type is no more than the number of operations of the first type minus $$$1$$$.
The optimal strategy — is to perform one operation of the first type, and then alternate operations of the first and second types, increasing the number of ones from $$$x$$$ to $$$2 \cdot (x + 1)$$$ on each such pair of operations. There is no point in doing more operations of the first type on the prefix of operations, since we still must cover no more than two segments of ones with operations of the second type; otherwise, we will reduce the possible number of operations of the second type.