Задача C. Карточный домик ≡

Условие

Карточный домик — конструкция, возводимая из игральных карт путём их установки рядами друг на друга особым способом. Целью является создание как можно более высокой структуры из карт, которая при этом бы не обрушилась. При строительстве карточных домиков не должен использоваться клей или какие-либо другие вспомогательные ингредиенты или приспособления, форма карт также не может меняться. Современным рекордсменом по строительству карточных домиков является Брайан Берг, чьи достижения были занесены в Книгу рекордов Гиннесса, сообщает Википедия.

Для достижения нового рекорда Брайан собирается построить домик высотой n этажей. Определите, сколько карт ему для этого понадобится.

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

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

Обратите внимание, что при заданных ограничениях для хранения ответа необходимо использовать 64-битный тип данных, например long long в C++, int64 в Free Pascal, long в Java.

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

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

Ограничения

1 ≤ n ≤ 10⁹

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

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

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

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

Смотри рисунок. Для постройки домика высотой 1 достаточно взять две карты и поставить их "шалашиком". Для домика высотой 3 понадобится уже 15 карт.

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

1

2

3

15