Олимпиадный тренинг

Задача . 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 позиции (элементы нумеруются с единицы).

Найдите число, находящееся на n-й позиции, если нумерация начинается с единицы.

Входные данные

В единственной строке находится целое число n (1 ≤ n ≤ 1014) — позиция числа, которое нужно найти.

Обратите внимание, что заданное число не помещается в 32-битном типе данных. Для сохранения числа вы можете использовать, например, тип long long в языке C++ или тип long в языке Java.

Выходные данные

Выведите n-й элемент последовательности (элементы нумеруются с единицы).


Примеры
Входные данныеВыходные данные
1 3
2
2 5
2
3 10
4
4 55
10
5 56
1

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя