Problem Description

Given a permutation of the sequence $(1, 2, \ldots, N)$ as $a_1, a_2, \ldots, a_N$.

You can color some elements of this sequence either red or blue, satisfying the following conditions:

• For all $i, j (1 \leq i < j \leq N)$, if both $ a_i $ and $ a_j $ are colored red, then $ a_i < a_j $.
• For all $i, j (1 \leq i < j \leq N)$, if both $ a_i $ and $ a_j $ are colored blue, then $ a_i > a_j $.

You want to color as many elements as possible.

Find the maximum number of elements that can be colored.

Input Format

The input is given from the standard input in the following format:

$ N $ $ a_1 $ $ a_2 $ \ldots $ a_N $

• The first line contains an integer $N (1 \leq N \leq 10^5)$.
• The second line contains the sequence $ a_i $ separated by spaces.
• $a_1, a_2, \ldots, a_N$ is a permutation of $(1, 2, \ldots, N)$.

Output Format

Output the maximum number of elements that can be colored in one line. The output should be to the standard output, and a newline should be added at the end.

Sample Input and Output

Sample Input #1

5
3 4 1 5 2

Sample Output #1

4

Sample Input #2

7
1 2 3 4 5 6 7

Sample Output #2

7

Sample Input #3

4
3 1 4 2

Sample Output #3

4

Sample Input #4

20
18 13 16 20 10 8 15 2 11 19 3 5 1 4 9 7 14 12 17 6

Sample Output #4

12

Notes/Hints

Sample Explanation 1

One example of a coloring method is to color $ a_1 $ and $ a_4 $ red, and $ a_2 $ and $ a_3 $ blue.

Sample Explanation 2

All elements can be colored red.

Sample Explanation 3

It is sufficient to color $ a_2 $ and $ a_3 $ red, and $ a_1 $ and $ a_4 $ blue.

见题面 Input 部分

见题面 Output 部分