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\ast {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