Задача E. Тефтели ≡

Условие

Карлсон обожает мясные тефтели. А ещё он обожает собирать башни из кубиков. Для каждой построенной Карлсоном башни Малыш считает число более низких башен, а потом складывает получившиеся величины. Карлсон получит от мамы Малыша столько тефтелек, чему будет равна эта сумма. Помогите Карлсону определить, какое наибольшее количество тефтелей он сможет получить, если у Малыша n кубиков?

Формат входных данных

Единственная строка входных данных содержит натуральное число n.

Обратите внимание, что значения переменных в этой задаче могут превышать возможные значения 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Формат выходных данных

Выведите одно неотрицательное целое число — ответ на вопрос задачи.

Ограничения

1 ≤ n ≤ 10⁹

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при n ≤ 100, получат не менее 40 баллов.

Пояснение к примеру

В примере дано n = 4. Переберем все возможные способы построения башен.

1) Одна башня высотой 4. Нет башен ниже её, сумма равна 0.

2) Две башни высотой 3 и 1. Одна башня ниже одной другой, сумма 1.

3) Две башни высотой 2 и 2. Все башни равной высоты, сумма 0.

4) Три башни высотой 2, 1 и 1. Для башни высоты 2 есть две башни ниже её, сумма 2.

5) Четыре башни высотой 1. Все башни равной высоты, сумма 0.

Примеры тестов

4

2