Description

Many years ago, Country A invented a missile system to intercept enemy missiles.

That system can, with a single interceptor missile, shoot down multiple enemy missiles whose heights are non-increasing from near to far.

Now, scientists have found that this defense system is not strong enough, so they invented another missile system.

This new system can, with a single interceptor missile, intercept more missiles from near to far.

When this system starts, it first selects one enemy missile to intercept; then it intercepts a farther missile with a lower height; then it intercepts a missile that is farther than the second one but has a higher height; and so on. In other words, among the intercepted missiles, every odd-numbered one (3rd, 5th, …) is farther and higher than the previous intercepted missile, and every even-numbered one (2nd, 4th, …) is farther and lower than the previous intercepted missile. All comparisons are strict.

Given a list of missile heights ordered from near to far, compute the maximum number of missiles that the new system can intercept with a single interceptor missile.

Input Format

The first line contains an integer $n$, the number of enemy missiles.
The second line contains $n$ integers, the heights of the missiles from near to far.

Output Format

Output a single integer, the maximum number of missiles that can be intercepted.

4
5 3 2 4

3

Hint

$1 \leq n \leq 10^3$.
For each $i$, $1 \leq h_i \leq 10^9$.

Translated by ChatGPT 5