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