题目描述

定义一组序列如下：

• $A_1 = (1)$
• $A_2 = A_1 + (2) + A_1 = (1, 2, 1)$
• $A_3 = A_2 + (3) + A_2 = (1, 2, 1,3,1,2,1)$
• $A_i = A_{i-1} + (i) + A_{i-1} = (1, \dots, 1,i,1,\dots,1)$

给定一个正整数 $N$，请输出 $A_N$ 的第 $N$ 项。

输入格式

输出格式

3

1

44

3

数据范围

• $30\%$ 的数据，$1\leq N\leq 2^{4}$
• $60\%$ 的数据，$1\leq N\leq 2^{20}$
• $100\%$ 的数据，$1\leq N\leq 2^{60}$