魔法序列
题号:NC274740
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

“如果世上只剩下一个女孩子,应该给她取名叫伊娜。”

伊娜从画板一侧探出半张小脸,用她湛蓝的眼眸盯了我好一会儿,才又缩了回去,几不可闻地轻叹了一声。

“你又在说怪话了。”伊娜小姐如是说。

“我是真心这么觉得的。”我告诉她。“因为伊娜的可爱已经达到前无古人后无来者的地步了。”


定义一个魔法序列 a 为:
\begin{cases}<br />a_1=1\\<br />a_i=\sum_{j<i}[a_j=a_{i-1}]&i>1<br />\end{cases}

具体来说,a 序列的第一项是 1,接下来每一项是上一项在该位置之前出现的次数。

给定一个正整数 n,你需要求出 \sum_{i=1}^n a_i

输入描述:

一行一个整数 n

数据保证:1\le n\le 10^9

输出描述:

一行一个整数,表示答案。
示例1

输入

复制
5

输出

复制
8

说明

序列的前 5 项分别是 [1,1,2,1,3],求和结果为 8