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}, \dots, a_r~. Độ lệch chuẩn của đoạn ~[l, r]~ là số lượng vị trí ~i~ (~l \le i \le r~) sao cho ~a_i \neq i - l + 1~. Hãy chia dãy ~a~ thành các đoạn sao cho mỗi phần tử ~a_i~ thuộc đúng một đoạn và tổng độ lệch chuẩn của các đoạn là nhỏ nhất.

Yêu cầu: Tìm tổng độ lệch chuẩn nhỏ nhất sau khi chia dãy.

Input

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 2 \times 10^5~) tương ứng là độ dài dãy ~a~.
• Dòng thứ hai chứa ~n~ số nguyên lần lượt là ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n, \forall 1 \le i \le n~) tương ứng với giá trị của các phần tử thuộc dãy ~a~.

Output

• Ghi trên một dòng duy nhất là tổng độ lệch chuẩn nhỏ nhất.

Sample Input 1

5
2 1 3 2 1

Sample Output 1

2