Incr

Background

Special for beginners, ^_^

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

1000ms, 256mb for each test case.

Hint

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