MECUNG

Cho một dãy gồm \(n\) số nguyên là một hoán vị của các số từ \(1\) đến \(n\). Dãy biểu diễn thứ tự các con số xuất hiện trên đường đi trong một mê cung.

Bạn cần thu thập đủ tất cả các số từ \(1\) đến \(n\) theo đúng thứ tự tăng dần \(1, 2, 3, \ldots, n\). Mỗi vòng di chuyển, bạn đi theo thứ tự của dãy từ đầu đến cuối; mỗi khi gặp số nhỏ nhất chưa được thu thập (tức là số lớn hơn đúng \(1\) đơn vị so với số vừa thu thập trước đó), bạn thu thập nó.

Hãy xác định số vòng di chuyển ít nhất cần thiết để thu thập đủ tất cả các số từ \(1\) đến \(n\).

Input

• Dòng đầu chứa số nguyên \(n\) (\(1 \le n \le 10^6\)).
• Dòng thứ hai chứa \(n\) số nguyên, là một hoán vị của \(1, 2, \ldots, n\).

Output

Một số nguyên duy nhất là số vòng di chuyển ít nhất cần thiết.

Scoring

• Subtask 1 (\(20\%\)): Dãy là hoán vị tăng dần hoặc giảm dần.
• Subtask 2 (\(30\%\)): \(n \le 10^3\).
• Subtask 3 (\(50\%\)): \(n \le 10^6\).

Sample Input 1

5
4 2 1 5 3

Sample Output 1

3

Notes

Vòng \(1\): thu thập \(1\). Vòng \(2\): thu thập \(2\) và \(3\). Vòng \(3\): thu thập \(4\) và \(5\).