Description

“咚。”

本杰明病了，此时他正在病床上玩积木，他将 $n$ 个高度不同的积木摆在面前并按顺序标为 $1 ~ n$ 号（可能会有高度相同的积木），本杰明突发奇想：现在有一次操作机会（可以不使用），操作可以将任一积木改变成任一高度，最终想让这 $n$ 块积木中的美丽序列长度最长。 本杰明病昏了，希望你来帮帮他。美丽序列的定义：设 $K$ 块积木从左到右编号为 $1$ ~ $K$，高度为 $a_{1}$ ~ $a_{K}$，则它们的高度满足 $a_{1} \leq ... \leq a_{i} \leq ... \leq a_{K}(1 \leq i \leq K)$​

Format

Input

第一行包含一个整数 $n(1 \leq n \leq 10^{6})$，表示积木的数量第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个数 $a_{i}(1 \leq a_{i} \leq 10^{9})$ 表示第 $i$ 块积木的高度

Output

输出一个整数表示最长美丽序列的长度

Samples

4
1 2 3 4

4

9
2 1 2 3 2 4 5 6 5

7

Hint