题目描述

有 $n$ 个海盗，编号为 $1,2,\cdots, n$，这些海盗都是绝顶聪明的人，并且他们都知道其他海盗也都是绝顶聪明的人。

现在他们要分一些金币。从编号为 $1$ 的海盗开始，每个人依次提出一个分配方案，接下来所有人（包括提出方案的人）选择赞成或者反对此方案，如果有至少一半人（恰好一半也可以）赞成则通过此方案，否则将这个人杀死并由下一个人继续提出分配方案。

每个海盗的第一目标都是保命，其次是拿到更多的金币，再其次是杀掉更多的人。

现在假设你是编号为 $1$ 的海盗，问金币数至少为多少时，你可以在存活下来的同时拿到至少 $1$ 枚金币。

注意：金币不可分割，只能给人分配整数枚金币。

输入格式

一行一个整数 $n$ 表示海盗的数量。

输出格式

一行一个整数表示答案。

样例

1

1

4

2

说明/提示

$1\le n \le 10^9$