题目描述

数据分析师岚把一个序列的“美丽值”定义为它的最长严格上升子序列长度。

现在给定一个长度为 $n$ 的数组 $a$。岚想从中选出一个子序列，使这个子序列的美丽值严格小于原数组 $a$ 的美丽值，并且这个子序列尽可能长。

请你求出这样的子序列的最大长度。

这里的子序列指可以从原数组中删除若干个元素后得到的序列，剩余元素的相对顺序不变。

输入格式

第一行包含一个整数 $n$，表示数组 $a$ 的元素个数。

第二行包含 $n$ 个整数

输出格式

输出一行一个整数，表示满足条件的子序列的最大长度。

数据范围

• $1\le n\le 5\cdot 10^5$；
• $1\le a_i\le 10^9$。

样例 1

输入

3
2 1 3

输出

2

样例 2

输入

4
4 3 2 1

输出

0

样例 3

输入

4
2 1 4 3

输出

2

样例 4

输入

6
4 6 5 2 1 3

输出

4

样例 5

输入

4
3 4 1 2

输出

2