Старша карта нижча карта (Платина)
Бесі та Ельза грають у просту карткову гру. Використовується колода з 2n карт, пронумерованих від 1 до 2n, яка ділиться на дві частини: n карт для Бесі та n карт для Ельзи. Гра складається з n раундів, у кожному з яких Бесі та Ельза викладають по одній карті. Спочатку, одне очко за раунд отримує гравець, чия карта більша. Однак, один раз за всю гру Бесі може змінити правила так, що до кінця гри очко за раунд отримуватиме гравець, чия карта менша. Бесі може вирішити не використовувати цю опцію, залишивши правило "виграє більша карта" на всю гру, або вона може активувати це правило перед першим раундом, і тоді вся гра проходитиме за правилом "виграє менша карта".
Знаючи порядок, у якому Ельза викладатиме свої карти, допоможіть Бесі визначити максимальну кількість очок, яку вона може заробити.
Вхідні дані
Перший рядок вводу містить значення n (2 ≤ n ≤ 50000).
Наступні n рядків містять карти, якими грає Ельза в тому порядку, в якому вона їх викладатиме в послідовних раундах гри. За цією інформацією можна легко визначити, які карти на руках у Бесі.
Вихідні дані
Виведіть один рядок, що містить максимальну кількість очок, яку може заробити Бесі.
Приклад
У Бесі карти 2, 5, 6, 7, і вона може заробити максимально 3 очка. Наприклад, вона може виграти у першої карти, а потім переключити правило на "менша карта виграє", і після цього вона може виграти ще два раунди.