题目描述

下面的图形是著名的杨辉三角形：

如果我们按从上到下、从左到右的顺序把所有数排成一列，可以得到如下数列：

$$1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \dots$$

给定一个正整数 $N$，请你输出数列中第一次出现 $N$ 是在第几个数。

输入格式

输入仅包含一行，一个正整数 $N$。

输出格式

输出一行，一个整数，代表 $N$ 在数列中第一次出现的序数。

样例输入 1

6

样例输出 1

13

说明

样例解释

在给出的数列 $1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, \dots$ 中，数字 $6$ 第一次出现是在第 $13$ 个位置，因此输出 $13$。

数据范围

• 对于 $20\%$ 的评测用例，保证 $1 \le N \le 10$。
• 对于 $100\%$ 的评测用例，保证 $1 \le N \le 10^9$。
• 保证所有的输入数值均为整数。