يوجد برج دائري لمواقف السيارات، فيه $N$ حجرة مرتبة في دائرة. تُسمى الحجرات 1 و2 و... و$N$ بالترتيب مع عقارب الساعة. تحتوي كل حجرة على سيارة واحدة. تحمل السيارة في الحجرة $i$ الرقم $a_i$.

للبرج زران. يؤدي ضغط A إلى تدويره حجرة واحدة مع عقارب الساعة، وضغط B إلى تدويره حجرة واحدة عكس عقارب الساعة. يبين الشكل الأيسر أدناه حالة المثال السابق بعد ضغط A، والأيمن حالته بعد ضغط B.

نريد إخراج جميع السيارات من البرج.

لا يمكن إخراج سيارة إلا من الحجرة الوحيدة الواقعة في الأسفل تمامًا. في البداية تكون الحجرة 1 في الأسفل. لإخراج سيارة من حجرة أخرى، يجب أولًا ضغط الأزرار بشكل مناسب لتدوير حجرتها إلى الأسفل.

إضافة إلى ذلك، قبل إخراج سيارة رقمها $x$، يجب إخراج جميع السيارات ذات الأرقام الأصغر من $x$. أي إنه ما دامت سيارة رقمها أقل من $x$ باقية في البرج، فلا يمكن إخراج سيارة رقمها $x$.

اكتب برنامجًا لإيجاد أقل عدد إجمالي من ضغطات الأزرار اللازمة لإخراج جميع السيارات.

القيود

• $1 \le N \le 100\,000$
• $1 \le a_i \le 1\,000\,000\,000$

المهام الفرعية

1. (8 نقاط) $a_i=1$ ($1\le i\le N$)، أي إن جميع السيارات تحمل الرقم 1.
2. (9 نقاط) $a_i\ne a_j$ عندما $i\ne j$، أي إن أرقام جميع السيارات مختلفة.
3. (10 نقاط) $N\le10$.
4. (21 نقطة) $N\le100$.
5. (31 نقطة) $N\le1\,000$.
6. (21 نقطة) لا توجد قيود إضافية.

الإدخال

يحتوي السطر الأول على عدد صحيح $N$.

يحتوي السطر الثاني على أرقام السيارات $a_1,\ldots,a_N$ بالترتيب، مفصولة بمسافات.

الإخراج

اطبع في السطر الأول أقل عدد إجمالي من ضغطات الأزرار.

أمثلة

الإدخال 1

4
1 2 2 1

الإخراج 1

3

ملاحظة

يمكن اتباع الترتيب: إخراج سيارة → الزر A → إخراج سيارة → الزر A → إخراج سيارة → الزر A → إخراج سيارة.

الإدخال 2

5
3 1 4 5 1

الإخراج 2

7