AlanashKO yêu tiền. Vào đêm giao thừa, cậu được tặng $N$ tờ tiền. Mệnh giá của mỗi tờ tiền là một số nguyên dương. Trong lúc chơi, AlanashKO xếp tất cả các tờ tiền thành một hàng và đánh số chúng từ trái sang phải từ $1$ đến $N$. Sau đó, cậu quyết định sắp xếp tất cả các tờ tiền theo thứ tự không giảm. Để làm điều này, AlanashKO thực hiện quy trình sau: trước tiên, cậu chia các tờ tiền thành một hoặc nhiều đoạn con không giao nhau, sao cho mỗi tờ tiền thuộc một đoạn con. Sau đó, lần lượt từ trái sang phải, các đoạn con được chèn vào một hàng mới: đoạn con ngoài cùng bên trái (đoạn con đầu tiên) được chèn trước, rồi đến đoạn con bên trái tiếp theo, và cứ như vậy. Mỗi đoạn con được chèn vào giữa hai tờ tiền bất kỳ hoặc vào một trong hai đầu của hàng mới hiện tại. Thứ tự các tờ tiền trong đoạn con không thay đổi khi chèn.
AlanashKO muốn số đoạn con nhỏ nhất có thể sao cho cuối cùng cậu sắp xếp được các tờ tiền theo thứ tự không giảm. Hãy giúp cậu tìm giá trị này.
Dữ liệu vào
Dòng đầu chứa một số nguyên dương $N$ ($1 \le N \le 10^6$) — số tờ tiền. Dòng tiếp theo chứa $N$ số nguyên dương $a_i$ ($1 \le a_i \le 10^6$) — mệnh giá của tờ tiền thứ $i$.
Dữ liệu ra
In trên một dòng một số nguyên — số đoạn con nhỏ nhất cho phép AlanashKO sắp xếp các tờ tiền.
Nhiệm vụ con
Bài này gồm bốn nhiệm vụ con:
- $N \le 8$. Được 9 điểm.
- $N \le 20$. Được 16 điểm.
- $N \le 300$. Được 20 điểm.
- $N \le 10^6$. Được 55 điểm.
Mỗi nhiệm vụ con chỉ được tính điểm nếu lời giải vượt qua thành công tất cả các nhiệm vụ con trước đó.
Ví dụ
Dữ liệu vào 1
6 3 6 4 5 1 2
Dữ liệu ra 1
3
Ghi chú
Đoạn con là một dãy các phần tử liên tiếp.
Hãy xét ví dụ:
Đáp án nhỏ nhất là chia thành 3 đoạn con: |3 6|4 5|1 2| (các vạch là ranh giới giữa các đoạn con).
Sau bước đầu tiên: hàng ban đầu là |4 5|1 2|, hàng mới là |3 6|.
Ở bước thứ hai, đoạn con |4 5| được chèn vào giữa $3$ và $6$.
Sau bước thứ hai: hàng ban đầu là |1 2|, hàng mới là |3 4 5 6|.
Sau đó, đoạn con |1 2| được chèn vào đầu hàng mới, thu được |1 2 3 4 5 6|.