← 返回题目列表

Codeforces · 2040/B

B. 画一条条

中文机器翻译题面 查看原题

你有一个长度为 $$$n$$$ 的零数组 $$$a_1, a_2, \ldots, a_n$$$。

您可以对其执行两种类型的操作:

1. 选择一个索引$$$i$$$,使得$$$1 \le i \le n$$$ 且$$$a_i = 0$$$,并将$$$1$$$ 赋值给$$$a_i$$$;
2. 选择一对索引 $$$l$$$ 和 $$$r$$$,使得 $$$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$$$,并将所有 $$$l \le i \le r$$$ 的 $$$1$$$ 分配给 $$$a_i$$$。

使数组的所有元素都等于 1 所需的第一类型操作的最少次数是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组的长度。

请注意,所有测试用例的 $$$n$$$ 总和没有限制。

输出

对于每个测试用例,打印一个整数 - 第一种类型所需操作的最小数量。

示例

输入 #1

4
1
2
4
20

输出 #1

1
2
2
4

注意

在第一个测试用例中,您可以使用 $$$i = 1$$$ 执行 $$$1$$$st 类型的操作。

在第二个测试用例中,您可以执行以下操作序列:

1. $$$1$$$st类型的操作,$$$i = 1$$$。执行此操作后,数组将如下所示:$$$[1, 0]$$$。
2. $$$1$$$st 类型的运算,$$$i = 2$$$。执行此操作后,数组将如下所示:$$$[1, 1]$$$。

第二个测试用例中的操作顺序

在第三个测试用例中,您可以执行以下操作序列:

1. $$$1$$$st类型的操作,$$$i = 1$$$。执行此操作后,数组将如下所示:$$$[1, 0, 0, 0]$$$。
2. $$$1$$$st类型的操作,$$$i = 4$$$。执行此操作后,数组将如下所示:$$$[1, 0, 0, 1]$$$。
3. $$$2$$$nd 类型的运算,$$$l = 1$$$,$$$r = 4$$$。在此段上,$$$a_l + \ldots + a_r = a_1 + a_2 + a_3 + a_4 = 2$$$,不小于$$$\lceil\frac{r - l + 1}{2}\rceil = 2$$$。执行此操作后,数组将如下所示:$$$[1, 1, 1, 1]$$$。

第三个测试用例中的操作顺序