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