题目描述

高中一年级的夏天，少年帆高离家出走，由小岛去到东京。

但他生活极之贫困，孤独度日，终于找到的一份工，却只是为一本古怪的「神秘学杂志」写稿。

跟着连日滂沱大雨，像是来映衬他的失落。 在纷纭杂沓的大都会一角，帆高遇上了一个可爱的少女阳菜。

阳菜和弟弟相依为命，个性坚强、开朗，但心中隐藏一个重大秘密──

她拥有一股不可思议的力量，她说：「现在开始天晴了！」

然后，雨渐渐停下来，美丽的阳光洒落到街上。 那原来是能让天空放晴的超能力……

有 $n$ 个人依次进入观影厅，观看 Weathering with You。

观影厅只有一排座位，第 $1$ 个人进入时，会选择第 $1$ 个座位坐下。

由于观影厅空调坏掉了，十分炎热，之后的每个人进入时，他会选择一个离最近的已经坐下的人尽可能远的空位。

如果有多个空位使得离最近的人同样远，则他会从其中随机选取一个。

若有两个人选择的位置相邻，他们就会不满意。

为了让所有人都满意，观影厅至少需要有几个座位呢？

输入格式

包含一行，仅一个正整数 $n$，表示前来观影的人数。

输出格式

包含一行，仅一个正整数，表示至少需要的座位数目。

4

8

数据范围与提示

对于 $100\%$ 的数据, $n\le 10^{1000}$。