← 返回题目列表

Codeforces · 268/B

B. 按钮

中文机器翻译题面 查看原题

Manao 正在尝试打开一把颇具挑战性的锁。锁上有n个按钮,要打开它,你应该按一定的顺序按下按钮才能打开锁。当您按下某个按钮时,它要么保持压入锁中(这意味着您已经猜对并按下了序列中的下一个按钮),要么所有按下的按钮都返回到初始位置。当所有按钮同时按下锁时,锁就会打开。

考虑一个具有三个按钮的示例。假设开头序列是:{2,3,1}。如果您首先按下按钮 1 或 3,按钮会立即松开。如果您首先按下按钮 2,它将保持按下状态。如果您在按 2 之后按 1,则所有按钮均会取消按下。如果您在按 2 之后按 3,按钮 3 和 2 将保持按下状态。一旦按下了两个按钮,您只需按下按钮 1 即可打开锁。

Manao 不知道开头顺序。但他真的很聪明,他会以最佳的方式行事。计算在最坏的情况下他需要按下按钮才能打开锁的次数。

输入

单行包含整数 n (1 ≤ n ≤ 2000) — 锁具有的按钮数量。

输出

在单行中打印 Manao 在最坏情况下按下按钮的次数。

示例

输入 #1

2

输出 #1

3

输入 #2

3

输出 #2

7

注意

考虑第一个测试样本。马纳奥可能会在第一次按下时失败并按下错误的按钮。在这种情况下,他在第二次推动时就已经能够猜到正确的了。他的第三次按下将按下第二个右侧按钮。因此,在最坏的情况下,他只需要推 3 次即可。