Cho dãy \((a)\) gồm \(n\) số nguyên, kí hiệu \(max(i)\) là số lớn nhất trong \(i\) số đầu tiên. Vỡi mỗi số nguyên dương \(i\), bạn có thể đổi số thứ \(i\) trong dãy thành \(max(i) + 1\).

Cần thực hiện ít nhất bao nhiêu lần đổi như vậy để thu được một dãy số tăng chặt ?

Đầu vào

Dòng đầu tiên chứa số nguyên \(n\), số phần tử của dãy số \((2 \le n \le 2*10^5)\).

Dòng tiếp theo chứa \(n\) số nguyên trong khoảng \([-10^6, 10^6]\), các phần tử của dãy số.

Đầu ra

Một số nguyên duy nhất là kết quả của bài toán.

Ví dụ

Đầu vào 1:

3
1 1 1

Đầu ra 1:

2

Giải thích: đổi số thứ \(2\) và số thứ \(3\) thu được dãy \(1, 2, 3\) tăng chặt.

Đầu vào 2:

8
1 2 5 2 6 8 6 3

Đầu ra 2:

4