Беси и Эльза играютв простую карточную игру. Берётся колода из 2n карт, последовательно пронумерованных 1..2n, и делится на две части по n карт для Беси и n карт для Эльзы. Затем они играют n раундов, в каждом из которых Беси и Эльза выкладывают по одной карте. Изначально, одно очко за каждый раунд выигрывает игрок, у которого карта больше. Однако однажды за всю игру Беси может переключить правила игры так, что до конца игры выигрывать одно очко за раунд будет игрок, карта которого меньше. Беси может также выбрать не использовать эту опцию, оставляя на всю игру правило "выигрывает бОльшая карта" или она может включить это правило перед первыми раундом, и тогда вся игра ведётся по правилу "выигрывает меньшая карта".

Зная порядок, в котором будет выкладывать свои карты Эльза, помогите Беси определить максимальное количество очков, которое она сможет заработать.

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

Первая строка ввода содержит значение n (2 ≤ n ≤ 50000).

Следующие n строк содержат карты которым играет Эльзав том порядке как она их будет выкладывать в последовательных раундах игры. Заметим, что по этой информации легко определить, какие карты на руках у Беси.

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

Выведите одну строку, содержащую максимальное количество очков, которое может заработать Беси.

Пример

У Беси карты 2, 5, 6, 7 и она может заработать максимально 3 очка. Например, она может выиграть у первой карты, а потом переключить правило на "меньшая карта выигрывает" и после этого она может выиграть ещё два раунда.