Missile Interception Problem

Many years ago, country A invented a missile defense system used to intercept enemy missiles. This system could launch a single missile to intercept multiple enemy missiles that are fired from near to far, with non‐increasing altitudes. Recently, scientists discovered that the old system was not powerful enough and invented a new missile system.

The new system works as follows:

1. It first intercepts an enemy missile (no condition on its altitude).
2. Then, it intercepts a missile that is farther away and has a lower altitude than the previous intercepted missile.
3. Then, it intercepts a missile that is even farther, but with a higher altitude than the missile intercepted in the previous step.
4. The process continues alternately: for the odd-numbered interceptions (3rd, 5th, etc.) the intercepted missile must be farther and have a higher altitude than the immediately preceding missile; for the even-numbered interceptions (2nd, 4th, etc.) the intercepted missile must be farther and have a lower altitude than the immediately preceding missile.

Formally, given a list of missiles sorted by increasing distance with altitudes \(a_1, a_2, \dots, a_n\), find the maximum number \(k\) such that there exists indices \(1 \le i_1 < i_2 < \cdots < i_k \le n\) satisfying:

• No condition for \(a_{i_1}\).
• If \(j\) is even then \(a_{i_j} < a_{i_{j-1}}\);
• If \(j > 1\) is odd then \(a_{i_j} > a_{i_{j-1}}\).

Your task is to compute the maximum number of missiles that can be intercepted by the new system in one launch.

inputFormat

The first line contains an integer \(n\) representing the number of enemy missiles. The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), which represent the altitudes of the missiles in order from closest to farthest.

outputFormat

Output a single integer representing the maximum number of missiles that can be intercepted by the new system.

sample

5
5 4 3 2 1

2