Hôm nay là ngày đầu tiên của năm ~2022~, các cửa hàng tiện lợi và siêu thị hoạt động rất tấp nập. Tường là nhân viên của một cửa hàng, hôm nay cửa hàng đón một vị khách thú vị. Nếu Tường có thể trả lời câu đố của vị khách này chính xác, cô bé sẽ được mừng tuổi từ người này.

Vị khách cho Tường một mảng ~a~ có ~n~ phần tử. Ở mỗi bước, chọn ~x~ là phần tử cuối cùng của mảng ~(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 gồm các phần tử không vượt quá ~x~ ~(\le x)~, còn phần bên phải gồm những phần tử lớn hơn hẳn ~x~ ~(> x)~. Thứ tự của các phần tử trong mỗi phần được giữ nguyên như trong mảng ban đầu. Mảng mới là phần bên trái nối với phần bên phải.

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

Vị khách cho biết sau một số bước nhất định mảng sẽ không thay đổi nữa. Tường được hỏi số bước biến đổi ít nhất là bao nhiêu để sau đó mảng được giữ nguyên.

Dữ liệu

• Dòng thứ nhất là số tự nhiên ~n~ ~(1 \le n \le 10^5)~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 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.

Ví dụ

Sample Input 1

5
2 4 1 5 3

Sample Output 1

1

Sample Input 2

5
5 3 2 4 1

Sample Output 2

2

Sample Input 3

4
1 1 1 1

Sample Output 3

0

Giải thích

• Ví dụ thứ nhất đã được trình bày trong đề, sau khi chọn ~x = 3~ thì mảng không thay đổi nên số lần biến đổi là ~1~.