Background

Special for beginners, ^_^

Description

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

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

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

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

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

Format

Input

输入共两行：

第一行，一个正整数表示 $n（\le300）$。

第二行，n 个正整数表示 $a_1, a_2, ... a_n（a_i\le10^9）$。

Output

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

Samples

6
4 3 5 1 6 2

1

Limitation

1s, 1024KiB for each test case.

Source

YACS 935

2024年5月月赛 乙组T4