Bạn được cho mảng hoán vị ~A~ gồm ~N~ phần tử được đặt trong một cái ống bán hình tròn như hình minh họa

Trong một thao tác bạn có thể lấy một phần tử ~A_i~ ~(1 \leq i \leq N)~ tại vị trí bất kỳ ra khỏi ống, nhưng bạn chỉ có thể thêm phần tử ~A_i~ vừa lấy đó vào ở tại ~2~ đầu ống.

Nhiệm vụ của bạn là hãy cho biết cần tối thiểu bao nhiêu thao tác trên để sắp xếp lại mảng ~A~ thành mảng tăng dần.

Input

Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \leq N \leq 10^6)~ là số lượng phần tử của mảng hoán vị ~A~.

Dòng thứ hai, chứa ~N~ số nguyên ~A_1, A_2,... A_N~ ~(1 \leq A_i \leq N)~ tương ứng với các phần tử của mảng hoán vị ~A~.

Output

Một số nguyên duy nhất là đáp án của bài toán.

Sample Input

4
1 3 2 4

Sample Output

2