题目描述

设 $\operatorname{sum}(S)$ 表示集合 $S$ 中所有元素的和。如果对于 $S$ 的任意两个不相交子集 $A$ 和 $B$，如果他们满足：

1. $\operatorname{sum}(A) \neq \operatorname{sum}(B)$
2. $|A|\leq |B|\lor\operatorname{sum}(A) > \operatorname{sum}(B)$

则称 $S$ 是 R 集合。现在我们假设有一个大小为 $n$，元素互不相等的集合，已经满足了条件 2，并且知道所有元素之间的大小关系。问最坏情况下最少需要几次比较才能确定它是不是 R 集合（修者按：比较是指选取两个集合判断它们的和是否相等）。

输入格式

输入的第一行包含一个整数 $n$。

输出格式

输出一个整数，表示最少比较次数。

样例输入

4

样例输出

1

样例说明

设这个 4 元集的元素是 $a_1<a_2<a_3<a_4$，那么我们只需要比较 $\operatorname{sum}\{a_1,a_4\}$ 和 $\operatorname{sum}\{a_2,a_3\}$

数据规模与约定

一共有 20 个数据，对于第 $i(1\leq i\leq 20)$ 个数据，$n=i\times 50$。