AlanashKO รักเงิน ในวันก่อนปีใหม่เขาได้รับธนบัตร $N$ ใบ มูลค่าของธนบัตรแต่ละใบเป็นจำนวนเต็มบวก ระหว่างเล่น AlanashKO วางธนบัตรทั้งหมดเรียงเป็นแถวและกำหนดหมายเลขจากซ้ายไปขวาตั้งแต่ $1$ ถึง $N$ จากนั้นเขาตัดสินใจเรียงธนบัตรทั้งหมดตามมูลค่าแบบไม่ลดลง โดยทำตามขั้นตอนต่อไปนี้: ก่อนอื่นเขาแบ่งธนบัตรออกเป็นช่วงย่อยที่ไม่ทับซ้อนกันหนึ่งช่วงหรือมากกว่า โดยธนบัตรแต่ละใบอยู่ในช่วงย่อยใดช่วงย่อยหนึ่ง จากนั้นเขานำช่วงย่อยทั้งหมดไปแทรกในแถวใหม่ทีละช่วงตามลำดับจากซ้ายไปขวา กล่าวคือ แทรกช่วงย่อยซ้ายสุด (ช่วงย่อยแรก) ก่อน แล้วจึงแทรกช่วงย่อยซ้ายสุดถัดไป และทำเช่นนี้ต่อไป แต่ละช่วงย่อยแทรกระหว่างธนบัตรสองใบใด ๆ หรือที่ปลายด้านใดด้านหนึ่งของแถวใหม่ในขณะนั้นได้ ลำดับธนบัตรภายในช่วงย่อยไม่เปลี่ยนแปลงเมื่อแทรก

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|