Migrated from Lutece 2991 a DP problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你知道DP吗？ 没错，就是Dancing with Pole。（精神错乱） $n$ 块积木从左往右排成一排，其中第 $i$ 块积木的高度为$a_i$。由于积木排列起来不够美观，因此老实人决定拿走一些积木，且不改变剩余积木的相对位置关系，使得剩余积木构成的新排列是美观的。 不妨假设剩下了 $m$ 块积木，第 $i$ 块高度为$b_i$，我们认为它是美观的，当且仅当存在一个 满足$1\le j\le m$ 的整数 $j$ 满足下面两个条件：

1. 对于满足 $1\le k \le j-1$ 的所有整数 $k$ 均有 $b_k<b_{k+1}$成立。
2. 对于满足 $j+1\le k \le m$的所有整数 $k$ 均有 $b_{k-1}>b_k$成立。

老实人希望拿走的积木数量最少，你能告诉他最少拿走多少块积木吗？

Input

输入第一行包含一个整数 $n$，表示最初的积木数量。 第二行包含 $n$ 个整数 $a_i$ ，第 $i$ 个整数表示从左往右第 $i$ 块积木的高度。

Output

输出包含一个非负整数，表示最少拿走多少块积木。

Samples

10
2 3 2 3 4 5 3 2 4 3

4

5
1 2 3 4 5

0

Constraints

$1\le n\le 3*10^5,1\le a_i\le n$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming