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

    所有蓝色元素组成的子序列是一个 严格上升子序列 ，

    所有红色元素组成的子序列是一个 严格下降子序列，

    并且使得染色无色的元素个数尽可能的少.

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

输入共两行：

第一行，一个正整数表示 n

第二行，n 个正整数表示 a_1,a_2,a_3,\dots,a_n

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

对于 30% 的数据，1≤n≤10

对于 60% 的数据，1≤n≤50,1≤a_i≤100

对于 100% 的数据，1≤n≤300,1≤a_i ≤10^9