5124. 选择

单点时限: 1.0 sec

内存限制: 256 MB

选择正确的道路出发吧。
—— 来自虚空的声音

给定一个初始序列 $\{1, 2, \dots, n\}$,你需要进行若干次操作,将整个序列所有数变成零。每个操作由三步组成:

  1. 选择一个下标集合 $S = \{i_1, i_2, \dots, i_k\} \subseteq \{1, 2, \dots, n\}$;
  2. 选择一个非负整数 $x$;
  3. 对每个选中的数减去 $x$:$\forall i \in S, a_i \leftarrow a_i - x$。

请计算在最优策略下需要的操作次数。

输入格式

输入一行一个正整数 $n ~ (1 \leq n \leq 10 ^ 6)$。

输出格式

输出一行一个正整数,表示最少需要的操作次数。

样例

Input
1
Output
1
Input
2
Output
2
Input
3
Output
2

提示

对于第三组样例,一种最优方案的两次操作如下:

  1. $S = \{1, 3\}, x = 1 : a = \{0, 2, 2\}$;
  2. $S = \{2, 3\}, x = 2 : a = \{0, 0, 0\}$.

可以证明,没有次数更少的方案。

610 人解决,691 人已尝试。

637 份提交通过,共有 1922 份提交。

1.5 EMB 奖励。

创建: 1 年,4 月前.

修改: 1 年,4 月前.

最后提交: 1 周,6 天前.

来源: N/A

题目标签