A5962. 天气之子 Tenki
编程题
普及-
知识点
题目描述
> 高中一年级的夏天，少年帆高离家出走，由小岛去到东京。
>
> 但他生活极之贫困，孤独度日，终于找到的一份工，却只是为一本古怪的「神秘学杂志」写稿。
>
> 跟着连日滂沱大雨，像是来映衬他的失落。 在纷纭杂沓的大都会一角，帆高遇上了一个可爱的少女阳菜。
>
> 阳菜和弟弟相依为命，个性坚强、开朗，但心中隐藏一个重大秘密──
>
> 她拥有一股不可思议的力量，她说：「现在开始天晴了！」
>
> 然后，雨渐渐停下来，美丽的阳光洒落到街上。 那原来是能让天空放晴的超能力……
有 $n$ 个人依次进入观影厅，观看 *Weathering with You*。
观影厅只有一排座位，第 $1$ 个人进入时，会选择第 $1$ 个座位坐下。
由于观影厅空调坏掉了，十分炎热，之后的每个人进入时，他会选择一个离最近的已经坐下的人尽可能远的空位。
如果有多个空位使得离最近的人同样远，则他会从其中随机选取一个。
若有两个人选择的位置相邻，他们就会不满意。
为了让所有人都满意，观影厅至少需要有几个座位呢？
>
> 但他生活极之贫困，孤独度日，终于找到的一份工，却只是为一本古怪的「神秘学杂志」写稿。
>
> 跟着连日滂沱大雨，像是来映衬他的失落。 在纷纭杂沓的大都会一角，帆高遇上了一个可爱的少女阳菜。
>
> 阳菜和弟弟相依为命，个性坚强、开朗，但心中隐藏一个重大秘密──
>
> 她拥有一股不可思议的力量，她说：「现在开始天晴了！」
>
> 然后，雨渐渐停下来，美丽的阳光洒落到街上。 那原来是能让天空放晴的超能力……
有 $n$ 个人依次进入观影厅，观看 *Weathering with You*。
观影厅只有一排座位，第 $1$ 个人进入时，会选择第 $1$ 个座位坐下。
由于观影厅空调坏掉了，十分炎热，之后的每个人进入时，他会选择一个离最近的已经坐下的人尽可能远的空位。
如果有多个空位使得离最近的人同样远，则他会从其中随机选取一个。
若有两个人选择的位置相邻，他们就会不满意。
为了让所有人都满意，观影厅至少需要有几个座位呢？
输入格式
包含一行，仅一个正整数 $n$，表示前来观影的人数。
输出格式
包含一行，仅一个正整数，表示至少需要的座位数目。
输入输出样例
输入 #1
4
输出 #1
8
说明/提示
| 测试点编号 | $n$ |
| :------------: | :---------------: |
| $1 \sim 2$ | $\le 5$ |
| $3 \sim 6$ | $\le 10^5$ |
| $7 \sim 10$ | $\le 10^{18}$ |
| $11 \sim 20$ | $\le 10^{1000}$ |
对于 $100\%$ 的数据, $n\le 10^{1000}$。
| :------------: | :---------------: |
| $1 \sim 2$ | $\le 5$ |
| $3 \sim 6$ | $\le 10^5$ |
| $7 \sim 10$ | $\le 10^{18}$ |
| $11 \sim 20$ | $\le 10^{1000}$ |
对于 $100\%$ 的数据, $n\le 10^{1000}$。