C. Загадка у костра
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Юрик оказался в лесу у костра, где собрались $$$n$$$ человек. Оказалось, что некоторые из них знакомы друг с другом. Для удобства пронумеруем людей целыми числами от $$$1$$$ до $$$n$$$. Обозначим как $$$d_i$$$ количество людей, сидящих у костра, с которыми знаком $$$i$$$-й человек. Неожиданно оказалось, что два человека с номерами $$$i$$$ и $$$j$$$ ($$$i \ne j$$$) знакомы друг с другом тогда и только тогда, когда $$$d_i = d_j$$$.

Вернувшись домой, Юрик задумался, какое минимальное количество пар людей могли быть знакомы, чтобы выполнялось это условие?

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

Единственная строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 5\,000$$$) — количество людей.

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

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

Примеры
Входные данные
4
Выходные данные
3
Входные данные
5
Выходные данные
4
Примечание

Рассмотрим первый пример из условия. Возможны следующие варианты:

  1. Любые два человека знакомы друг с другом. В этом случае количество пар знакомых людей равно $$$\frac{4 \cdot 3}{2} = 6$$$.
  2. Некоторые три человека попарно знакомы друг с другом, четвертый человек не знаком ни с кем. В этом случае количество пар знакомых людей равно $$$3$$$.