该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个长度为 $n$ 的序列 $\{a_1,a_2,\cdots,a_n\}$，每次操作允许你从中删除一个数，再把他插入到任意位置。

问，你最少需要几次操作可以把这 $n$ 个数的序列变成是从小到大的非递减序列。

输入格式

第一行是输入一个整数 $n$ 表示序列元素个数。

第二行包含 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

输出格式

输出一行一个数表示最小操作次数。

样例

3
1 2 3

0

5
10 30 20 30 10

2

6
1 1 1 2 3 1

1

说明提示

对于 $50\%$ 的数据，保证 $n\le 5000$

对于 $100\%$ 的数据，保证 $n\le 10^5,1\le a_i \le 10^9$。