Sắp xếp dãy số

Cho một dãy gồm \(n\) số nguyên, số thứ \(i\) có giá trị \(a_i\). Bạn có thể sắp xếp lại dãy số nhiều nhất một lần bằng cách chọn một số các số liên tiếp cuối cùng trong dãy, giữ nguyên trình tự đã có của các số được chọn, chuyển lên đầu dãy đã cho. Sau đó bạn chỉ định một số làm điểm xuất phát và số này sẽ bị loại ra khỏi dãy. Tiếp theo, lần lượt số gần nhất bên phải số bị loại và có giá trị lớn hơn số đã bị loại ngay trước đó cũng sẽ bị loại ra khỏi dãy.

Ví dụ: với dãy các số \(2, 4, 1, 3, 3\) bạn có thể chọn \(3\) số cuối và di chuyển lên đầu dãy, ta sẽ nhận được dãy mới là \(1, 3, 3, 2, 4\), sau đó chỉ định điểm xuất phát là số đầu tiên, như vậy bạn sẽ loại được \(3\) số: \(1\), \(3\), \(4\).

Yêu cầu: Hãy xác định số lượng các số bị loại nhiều nhất.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 2 \times 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\), \(1 \le i \le n\)).

Ràng buộc:

• Có \(20\%\) số điểm thỏa mãn điều kiện \(1 \le n \le 1000\);

• Có \(80\%\) số điểm thỏa mãn điều kiện \(1000 < n \le 2 \times 10^5\).

Output

In ra một số nguyên là số lượng các số bị loại nhiều nhất.

Example 1

Input:

5
2 4 1 3 3

Output:

3

Example 2

Input:

5
1 2 3 3 5

Output:

4

Note

Ở ví dụ thứ nhất, chuyển \(3\) số cuối lên đầu được dãy \(1, 3, 3, 2, 4\). Xuất phát từ số \(1\), số gần nhất bên phải lớn hơn \(1\) là số \(3\) đầu tiên, tiếp theo số gần nhất lớn hơn \(3\) là số \(4\). Loại được \(3\) số, không thể loại được nhiều hơn.

Ở ví dụ thứ hai, không cần sắp xếp lại. Xuất phát từ số \(1\) đầu tiên, ta loại lần lượt các số \(1, 2, 3, 5\), tổng cộng \(4\) số. (Số \(3\) thứ hai không bị loại vì nó không lớn hơn \(3\).)