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

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

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

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

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

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

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

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