Độ xấu nhỏ nhất

Cho dãy \(a\) gồm \(n\) phần tử. Đoạn \([l, r]\) của dãy \(a\) là dãy gồm các phần tử liên tiếp \(a_l, a_{l+1}, \ldots, a_r\).

Độ xấu của đoạn \([l, r]\) được định nghĩa là số lượng chỉ số \(i\) thỏa mãn \(l \le i \le r\) sao cho \(a_i \ne i - l + 1\).

Hãy chia dãy \(a\) thành một số đoạn (không giao nhau, mỗi phần tử thuộc đúng một đoạn) sao cho tổng độ xấu của tất cả các đoạn là nhỏ nhất.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \le n \le 2 \times 10^5)\) --- độ dài của dãy \(a\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \le a_i \le n)\) --- các phần tử của dãy.

Output

• In ra một số nguyên duy nhất --- tổng độ xấu nhỏ nhất có thể đạt được sau khi chia dãy thành các đoạn.

Example

5
2 1 3 2 1

2

Scoring

• Subtask 1 (25 điểm): \(n \le 200\)
• Subtask 2 (25 điểm): \(n \le 3000\)
• Subtask 3 (25 điểm): \(a_i \le 200\)
• Subtask 4 (25 điểm): Không có ràng buộc bổ sung