You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

给定有 n 个数的 A 序列：$A_1,A_2,A_3\cdots A_n$。对于这个序列，我们想得到一个子序列

$A_{p_1}, A_{p_2} \cdots A_{p_i} \cdots A_{p_m}(1 \le p_1 < p_2<\cdots p_i < \cdots < p_m \le n)$，

满足 $A_{p_1} \ge A_{p_2} \ge \cdots \ge A_{p_i} \le \cdots \le A_{p_m}$。

从 A 序列最少删除多少元素，可以得到我们想要的子序列。

输入格式

第一行输入一个整数 n，代表 A 序列中数字的个数。 第二个输入 n 个整数，代表$A_1,A_2,A_3...A_n$。 $(1 \leq n \leq 1000，1 \leq A_i \leq 10000$

输出格式

输出需要删除的元素个数，占一行。

样例输入

7
3 2 4 1 2 5 3

样例输出

2

查看提示 提示 可以从前往后做一次最长不升子序列，在从后往前做最长不上升子序列。分别记录从前往后以第 i 个元素为结尾的最长不升子序列长度 dp1[i]，和从后往前以第 i 个元素为结尾的最长不升子序列长度 dp2[i]。这样 dp1[i] + dp2[i] - 1 就是得到的 B 序列的长度。