题目描述

数列 A1,A2,...,AN，修改最少的数字，使得数列严格单调递增。

输入格式

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

输出格式

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

样例

input

3
1 3 2

output

1

提示

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