← 返回题目列表

Codeforces · 622/A

A. 无限序列

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

考虑整数的无限序列: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