考虑整数的无限序列:1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5....该序列是按以下方式构建的:首先写出数字1,然后写出1到2的数字,然后写出1到3的数字,然后写出1到4的数字,依此类推。请注意,该序列包含数字,而不是数字。例如,数字 10 首先出现在序列中的位置 55(元素从 1 开始编号)。
查找序列第 n 个位置上的数字。
输入
唯一一行包含整数 n (1 ≤ n ≤ 1014) — 要查找的数字的位置。
请注意,给定的数字太大,因此您应该使用 64 位整数类型来存储它。在 C++ 中,您可以使用 long long 整型,在 Java 中,您可以使用 long 整型。
输出
打印序列中第 n 个位置的元素(元素从 1 开始编号)。
示例
输入 #1
3
输出 #1
2
输入 #2
5
输出 #2
2
输入 #3
10
输出 #3
4
输入#4
55
输出#4
10
输入 #5
56
输出 #5
1