Cho dãy số nguyên \(a_1,a_2,...,a_n\), ta sắp xếp lại dãy thành dãy không tăng bằng các bước như sau:

• Tìm số \(i\) nhỏ nhất thỏa mãn tồn tại số \(j\) sao cho \(i < j\) và \(a_i < a_j\).
• Nếu tồn tại số \(i\) như vậy, chuyển số \(a_i\) về cuối dãy.
• Nếu không tồn tại số \(i\) như vậy, kết thúc chương trình.

Yêu cầu: Cho dãy số nguyên ban đầu, hãy tính số bước cần thực hiện.

Input

• Dòng đầu gồm số nguyên \(n\) (\(1 \le n \le 3 \times 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(a_i \le 10^9\)).

Output

• Một số duy nhất là số bước cần thực hiện.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 500\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 5000\).
• Subtask \(3\) (\(20\%\) số điểm): \(a_i \le 3\).
• Subtask \(4\) (\(20\%\) số điểm): \(a_1 \le a_2 \le ... \le a_n\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

6
2 4 3 1 2 3

4