Поиск

Кольцевая линия


Ограничение времени     1 секунда
Ограничение памяти 256Mb
Ввод circle.in
Вывод circle.out

В городе, в котором живут друзья Андрей и Борис, метро состоит из единственной кольцевой линии, вдоль которой на равном расстоянии друг от друга расположены n станций, пронумерованных от 1 до n. Участок линии метро между двумя соседними станциями называется перегоном.

Поезда по кольцевой линии двигаются как по часовой стрелке, так и против часовой стрелки, поэтому чтобы добраться от одной станции до другой, пассажир может выбрать то направление, в котором требуется проехать меньше перегонов. Минимальное число перегонов, которое необходимо проехать, чтобы добраться от одной станции до другой, назовем расстоянием между станциями.

Друзья заметили, что выполняется следующее условие: если загадать некоторую станцию X и выписать для нее два числа: Da — расстояние от станции, на которой живет Андрей, до станции X и Db — расстояние от станции, на которой живет Борис, до станции X, то полученная пара чисел [Da, Db] будет однозначно задавать станцию X.

Например, если n = 4, Андрей живет на станции 1, а Борис живет на станции 2, то станция 1 задается парой [0, 1], станция 2 — парой [1, 0], станция 3 — парой [2, 1] и станция 4 — парой [1, 2].

Их одноклассник Сергей живет в соседнем городе и не знает, на каких станциях живут Андрей и Борис. Чтобы найти друзей, он заинтересовался, сколько существует вариантов пар станций A, B, таких что если Андрей живет на станции A, а Борис — на станции B, то выполняется описанное выше условие.

Требуется написать программу, которая по числу станций n на кольцевой линии определяет искомое количество вариантов.

Формат ввода

Первая строка входного файла содержит одно целое число n (3 ≤ n ≤ 40 000).

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

Выходной файл должен содержать одно число — искомое количество вариантов.

Пример 1

Ввод

4

Вывод

8

Пример 2

Ввод

5

Вывод

20

Примечания

В первом примере подходят следующие варианты:

  • Андрей живет на станции 1, а Борис на станции 2;
  • Андрей живет на станции 1, а Борис на станции 4;
  • Андрей живет на станции 2, а Борис на станции 1;
  • Андрей живет на станции 2, а Борис на станции 3;
  • Андрей живет на станции 3, а Борис на станции 2;
  • Андрей живет на станции 3, а Борис на станции 4;
  • Андрей живет на станции 4, а Борис на станции 1;
  • Андрей живет на станции 4, а Борис на станции 3.

Система оценки и описание подзадач
В этой задаче три подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи успешно пройдены.

Подзадача 1 (25 баллов)
3 ≤ n ≤ 50.

Подзадача 2 (25 баллов)
3 ≤ n ≤ 500.

Подзадача 3 (50 баллов)
3 ≤ n ≤ 40 000.

Получение информации о результатах окончательной проверки)
По запросу сообщается результат окончательной проверки на каждом тесте.

Для отправки решения задачи необходимо авторизоваться!