题目描述

有 $n$ 个海盗被编号为 $1\sim n$，并且他们都是绝对理智的，并且他们都知道他们都是绝对理智的，等等。

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

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

现在你编号为 $1$ 的海盗，求金币数至少为多少时，你可以活下来。你可以为了活命不给自己分配任何金币。

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

输入格式

一行一个整数 $n$，$1\le n\le 10^9$。

输出格式

一行一个整数表示答案。

1

0

3

1

99

49