يحب 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|$.