בהינתן מערך מספרים שלמים $A$ בגודל $N$, פעולת ערבוב מוגדרת כך:

• בתחילה יוצרים מערך מספרים שלמים ריק $B$.
• לאחר מכן, כל עוד $A$ אינו ריק, מסירים את האיבר השמאלי ביותר או הימני ביותר של $A$, ומוסיפים את ערכו לקצה הימני של $B$.
• אם $A$ ריק, מחליפים את $A$ ב-$B$ ועוצרים.

אם פעולת הערבוב מתבצעת כפי שמוצג באיור שלעיל, ערכו של המערך $A$ משתנה באופן הבא:

$$ (34,19,5,36,4,25,12,9)\to(9,34,19,12,25,4,5,36). $$

יהי $A_i$ האיבר ה-$i$ של המערך $A$. כאשר מתקיים התנאי ״אם $1 \le i<j \le N$, אז $A_i \le A_j$״, אומרים שהמערך $A$ עולה מונוטונית.

כתבו תוכנית שבהינתן מערך מספרים שלמים $A$ בגודל $N$, מחשבת את מספר פעולות הערבוב המינימלי הנדרש כדי להפוך את המערך $A$ לעולה מונוטונית.

קלט

השורה הראשונה של הקלט מכילה מספר שלם אחד $N$, מספר האיברים במערך $A$ ($1 \le N \le 3\cdot10^5$).

השורה השנייה מכילה $N$ מספרים שלמים $A_1,\ldots,A_N$: הערכים ההתחלתיים של איברי המערך $A$ ($1 \le A_i \le 10^9$).

פלט

הדפיסו את מספר פעולות הערבוב המינימלי הנדרש כדי להפוך את המערך $A$ לעולה מונוטונית.

דוגמאות

קלט 1

3
2 2 5

פלט 1

0

קלט 2

6
1 5 8 10 3 2

פלט 2

1