Cho số nguyên \(n\) và dãy số nguyên \(a_1,a_2,…,a_n\). Một phép biến đổi trên dãy \(a_1,a_2,…,a_n\) như sau:

• Chọn ra một số \(x=a_n.\)

• Sau đó mảng \(a\) bị chia làm hai phần: trái và phải.

  • Phần bên trái bao gồm các phần tử \(≤x.\)

  • Phần bên phải bao gồm các phần tử\( >x.\)

  • Thứ tự mỗi phần được giữ nguyên như trong mảng ban đầu.

Yêu cầu: Tính số phép biến đổi ít nhất để dãy không còn thay đổi được nữa (giữ nguyên).

Input

• Dòng thứ nhất chứa số nguyên \(n (1≤n≤10^5 ).\)

• Dòng thứ hai chứa \(n\) số nguyên \(a_1,a_2,…,a_n (1≤a_i≤10^9 ).\)

Output

• In ra số phép biến đổi ít nhất cần tìm.

Sample Input

5
2 4 1 5 3

Sample Output

1

Sample Input

5
5 3 2 4 1

Sample Output

2

Sample Input

4
1 1 1 1

Sample Output

0

Giải thích

• Ví dụ thứ nhất sau khi chọn x=a_n=3, thì dãy mới thu được: 2 1 3 4 5. Dãy 2 1 3 4 5 không biến đổi được nữa, mất 1 phép biến đổi.