思路

如果数组长度小于或等于2，操作次数就是数组长度，其余情况是前两次操作会染两个，第三次操作开始，为了最小化操作次数，则需要每次操作染色尽可能多，所有如果当前有x个染色块，则最多可以新增染色x-1个，所有每次贪心染色x-1个，直到全部染色完。

代码

python

题目内容

小美正在对一个长度为n的数组a进行染色。初始时所有元素均为无色。他每次可以选择以下操作之一：

• 选择一个索引将其染成红色。

• 选择一个区间[$l,r$]，如果该区间内红色元素的个数多于无色元素的个数，则将这个区间内的所有元素全部染成红色。

  小美至少需要多少次操作，才能将整个数组全部染成红色？

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤10^5$)代表数据组数，每组测试数据描述如下: 在一行上输入一个整数$n$($1≤n≤10^9$)代表数组中的元素数量。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表将整个数组全部染成红色所需的最少操作次数。

样例1

输入

3
3
4
12

输出

3
4
6