题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，你可以给序列中的每个元素染成 蓝色，红色，无色 中的某一种颜色，使得：

• 所有蓝色元素组成的子序列是一个 严格上升子序列 ，
• 所有红色元素组成的子序列是一个 严格下降子序列，
• 并且使得染色无色的元素个数尽可能的少。

请问最优情况下，无色的元素个数最少是多少？

输入格式

输入共两行： 第一行，一个正整数表示 $n$ 第二行，$n$ 个正整数表示 $a_1,a_2,...,a_n$

输出格式

输出共一行，一个整数表示答案

6
4 3 5 1 6 2

1

样例解释 1

蓝色：4 5 6 红色：3 1 无色：2

数据范围

• 对于 $30\%$ 的数据，$1 \leq n \leq 10$
• 对于 $60\%$ 的数据，$1 \leq n \leq 50,1 \leq a_i \leq 100$
• 对于 $100\%$ 的数据，$1 \leq n \leq 300,1 \leq a_i \leq 10^9$