Старша картка молодша картка (Платина)#11164
Бессі та її подруга Елсі зараз грають у просту карткову гру. Вони беруть колоду з карток, пронумерованих від до , і ділять її порівну, так що кожен гравець отримує по карток. Потім вони грають раундів, у кожному з яких Бессі та Елсі викладають по одній картці.
Спочатку гравець, який викладає картку з більшим номером, отримує одне очко. Однак у будь-який момент гри Бессі може вирішити змінити правила так, щоб до кінця гри очко отримував гравець, який викладає картку з меншим номером. Бессі може не використовувати цю можливість, залишивши всю гру в режимі перемагає "старша картка", або може змінити правила одразу, змусивши всю гру проходити за правилом перемагає "молодша картка".
Оскільки Бессі знає порядок, у якому Елсі буде викладати свої картки, визначте максимальну кількість очок, яку Бессі може набрати.
У першому рядку міститься ціле число n~(2 \le n \le 50000).
У наступних рядках містяться картки, які Елсі буде викладати в кожному з послідовних раундів гри. Зауважте, що за цією інформацією можна визначити картки Бессі.
Виведіть максимальну кількість очок, яку може набрати Бессі.
У цьому прикладі у Бессі на руках картки та , і вона може набрати не більше очок. Наприклад, Бессі може протягом усієї гри дотримуватися правила "перемагає старша картка". Вона може перемогти картку своєю карткою , програти картці , зігравши , а потім перемогти картки і , зігравши відповідно і , набравши загалом очки.
Приклад 1