ТПУ: основной тур

Соревнование завершилось 15.04.18 в 16:00

E. Добрый гном

Ограничение по времени: 1 с.
Ограничение по памяти: 64 МБ

Добрый гном закопал клад на клетчатом поле размера n \times n. Гном пронумеровал случайным образом все клетки целыми последовательными числами от 1 до n^{2} так, что каждая клетка имеет уникальный номер. Добрый гном проболтался, что клад закопан в одной из клеток поля.

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

  • Паша находит клад;

  • Паша не находит клад, а гном подсказывает, что клад находится в клетке с большим номером;

  • Паша не находит клад, а гном подсказывает, что клад находится в клетке с меньшим номером.

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

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

Единственная строка входных данных содержит одно целое число n — длину стороны поля гнома (1 \leqslant n \leqslant 10^{6}).

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

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

Примеры
Стандартный вводСтандартный вывод
45