Беси и Эльза играютв простую карточную игру. Берётся колода из \(2N\) карт,
последовательно пронумерованных \(1 \ldots 2N\), и делится на две части по
\(N\) карт для Беси и \(N\) карт для Эльзы. Затем они играют \(N\) раундов,
в каждом из которых Беси и Эльза выкладывают по одной карте. Изначально,
одно очко за каждый раунд выигрывает игрок, у которого карта больше.
Однако однажды за всю игру Беси может переключить правила игры так, что
до конца игры выигрывать одно очко за раунд будет игрок, карта которого
меньше. Беси может также выбрать не использовать эту опцию, оставляя на всю игру правило "выигрывает бОльшая карта" или она может включить это правило перед первыми раундом, и тогда вся игра ведётся по правилу "выигрывает меньшая карта".
Зная порядок, в котором будет выкладывать свои карты Эльза, помогите Беси
определить максимальное количество очков, которое она сможет заработать.
ФОРМАТ ВВОДА (файл cardgame.in):
Первая строка ввода содержит значение N (
\(2 \leq N \leq 50,000\)).
Следующие N строк содержат карты которым играет Эльзав том порядке как
она их будет выкладывать в последовательных раундах игры. Заметим, что по
этой информации легко определить, какие карты на руках у Беси.
ФОРМАТ ВЫВОДА (файл cardgame.out):
Выведите одну строку, содержащую максимальное количество очков, которое
может заработать Беси.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
8
4
3
|
3
|