Cho mảng \(a\) gồm \(n\) phần tử bất kì. Ở mỗi bước chọn ra một số \(x (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ử không vượt quá \(x(≤ x)\) trong khi đó phần bên phải sẽ là những số lớn hơn hẳn \(x(> x)\). Thứ tự của mỗi phần tử trong mỗi phần được giữ nguyên trong mảng ban đầu.

Ví dụ, với mảng \([2, 4, 1, 5, 3]\) sẽ chọn \(x = 3\), sau đó mảng trở thành \(2\) phần \([2, 1, 3]\), \([4, 5]\)

Dãy thu được −> \([2, 1, 3, 4, 5]\) -> Dãy này sẽ không biến đổi được nữa.

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

Dữ liệu

• Dòng thứ nhất là số tự nhiê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)\).

Kết quả

• In ra một số \(k\) là số bước biến đổi ít nhất để mảng không thay đổi.

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