Description

铭铭在刘宝宝不在的时候偷偷用它的电脑生成了一个随机数列A1,A2,...,AN，铭铭是一个有强迫症的人，他不需得把这个数列修改成单调递增的，现在他想求修改最少的次数，使得数列严格单调递增，于是他边把这个问题交给了你去解决。

Format

Input

第 1 行，1 个整数 N
第 2 行，N 个整数 A1,A2,...,AN

Output

1 个整数，表示最少修改的次数

Sample 1

Input

3
1 3 2

Output

1

Limitation

对于 50% 的数据，N ≤ 10^3
对于 100% 的数据，1 ≤ N ≤ 10^5,1 ≤ Ai ≤ 10^9