题目描述

世界的大小是 $n$ 格。每一格有一个权值。需要去掉一些格子，使得权值为从左到右上升的。最多保留多少个格子？

输入格式

第一行，一个整数 $n$，表示世界的大小。

第二行有 $n$ 个整数，第 $i$ 个整数表示从左到右第 $i$ 格的权值。

输出格式

一个整数表示答案。

6
1 2 4 1 3 4

4

提示

样例解释

去掉第三格和第四格。

数据范围

$n$ 不超过 $5000$，所有整数不超过 ${10}^9$。