题目描述

展览馆把 $n$ 张标签按顺序排成一行，第 $i$ 张标签上的编号为 $a_i$。馆长希望保留下来的标签编号严格递增（相邻保留编号必须满足前一个小于后一个）。

管理员只能执行至多一次操作：选取一个连续区间，一次性移除这个区间的全部标签。也可以不移除任何标签。移除后，区间左边的标签与区间右边的标签会直接相邻，且原有相对顺序不变。

请计算至少需要移除多少张标签。允许把所有标签移除，此时空序列视为严格递增。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

一行一个整数，表示最少移除的标签数量。

样例 1

6
1 4 3 5 2 6

3

样例解释

移除第 $3$ 至第 $5$ 张标签（编号 $3,5,2$），剩余 $1,4,6$，严格递增，移除 $3$ 张。无法只移除更短的一个连续区间使序列严格递增。

数据范围与部分分

保证 $1\le n\le2\times10^5$，$-10^9\le a_i\le10^9$。编号可以重复或为负数。

“严格递增”意味着相同的相邻编号也不合法。