### 问题描述

最长上升子序列（Longest Increasing Subsequence），简称 LIS，指的是一个序列中最长的一个子序列，满足其单调递增。

例如，对于一个序列 $a_1, a_2, a_3, a_4,...,a_i,...,a_n$，存在一个序列 $b_1, b_2,..., b_m$，满足：

1. $1 \le b_1 \lt b_2 \lt ... \lt b_m \le n$。
2. $a_{b_1} \lt a_{b_2} \lt ... \lt a_{b_m}$。

那么我们称 $\lbrace a_{b_1} , a_{b_2} , ... , a_{b_m} \rbrace$ 为 $\lbrace a_i \rbrace$ 的一个上升子序列。

最长的上升子序列就是最长（元素数量最多）的一个上升子序列。

小蓝学到了这个知识点，并且学会一些用来计算 LIS 的常见算法。

于是小蓝向邻居小桥炫耀他学到的新知识，但是小桥显然不会让小蓝如此得意，于是他提出了一个新的问题：

给定一个长度为 $n$ 的序列 $\lbrace a_i \rbrace$，小蓝可以选择其中的一个位置，修改为 $0 \sim 10^{100}$ 中的任何一个整数。具体来说，小蓝可以选择一个位置 $p(p \in [1, n])$，将 $a_p$ 重新赋值为 $0 \sim 10^{100}$ 中的任意一个整数。请问修改过后，最长上升子序列的长度是多少？

小蓝看到这个问题，两眼一抹黑，于是请你帮他解决这个问题。

输入格式

第一行输入一个整数 $n$。

第二行输入 $n$ 个整数 $a_1, a_2, ..., a_i, ... ,a_n$，用来表示序列 $a$ 的每个值。

输出格式

输出一个整数，表示修改后的最长上升子序列长度。

样例输入

5
2 5 4 3 7

样例输出

4

说明

修改 $3$ 为 $5$，得到 $2,5,4,5,7$，得到最长上升子序列为 $2,4,5,7$。

评测数据范围

$1 \le n \le 5 \times 10^3, 0 \le a_i \le 10^9$。