AlanashKO אוהב כסף. בערב השנה החדשה הוא קיבל $N$ שטרות. הערך הנקוב של כל שטר הוא מספר שלם חיובי. במהלך משחק, AlanashKO סידר את כל השטרות בשורה ומספֵּר אותם משמאל לימין מ־$1$ עד $N$. לאחר מכן החליט למיין את כל השטרות בסדר לא יורד.

לשם כך AlanashKO מבצע את התהליך הבא: תחילה הוא מחלק את השטרות לתת־קטעים זרים אחד או יותר, כך שכל שטר שייך לתת־קטע כלשהו. לאחר מכן הוא מכניס את תתי־הקטעים, בזה אחר זה לפי סדרם משמאל לימין, לשורה חדשה: תחילה מוכנס תת־הקטע השמאלי ביותר (תת־הקטע הראשון), אחריו תת־הקטע הבא משמאל, וכן הלאה. כל תת־קטע מוכנס בין שני שטרות כלשהם או באחד משני קצותיה של השורה החדשה הנוכחית. סדר השטרות בתוך תת־הקטע אינו משתנה בעת הכנסתו.

AlanashKO רוצה למזער את מספר תתי־הקטעים כך שבסופו של דבר יוכל למיין את השטרות בסדר לא יורד. עזרו לו למצוא ערך זה.

קלט

השורה הראשונה מכילה מספר שלם חיובי יחיד $N$ ‏($1 \le N \le 10^6$) — מספר השטרות. השורה הבאה מכילה $N$ מספרים שלמים חיוביים $a_i$ ‏($1 \le a_i \le 10^6$) — ערכו של השטר ה־$i$.

פלט

הדפיסו בשורה אחת מספר שלם יחיד — המספר המזערי של תתי־קטעים המאפשר ל־AlanashKO למיין את השטרות.

ניקוד

משימה זו כוללת ארבע תתי־משימות:

1. $N \le 8$. שווה 9 נקודות.
2. $N \le 20$. שווה 16 נקודות.
3. $N \le 300$. שווה 20 נקודות.
4. $N \le 10^6$. שווה 55 נקודות.

כל תת־משימה תזכה בניקוד רק אם הפתרון עובר בהצלחה את כל תתי־המשימות הקודמות.

דוגמאות

קלט 1

6
3 6 4 5 1 2

פלט 1

3

הערה

תת־קטע הוא רצף של איברים סמוכים.

נבחן את דוגמת הבדיקה:

התשובה המזערית היא חלוקה ל־3 תתי־קטעים: |3 6|4 5|1 2| (הקווים מסמנים את גבולות תתי־הקטעים).

לאחר הצעד הראשון: השורה המקורית היא |4 5|1 2|, והשורה החדשה היא |3 6|.

בצעד השני מוכנס תת־הקטע |4 5| בין $3$ ל־$6$.

לאחר הצעד השני: השורה המקורית היא |1 2|, והשורה החדשה היא |3 4 5 6|.

לאחר מכן מוכנס תת־הקטע |1 2| לתחילת השורה החדשה, והתוצאה היא |1 2 3 4 5 6|.