P3903 Missile Interception III

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.

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 a single integer, the maximum number of missiles that can be intercepted.

$1 \leq n \leq 10^3$. For each $i$, $1 \leq h_i \leq 10^9$. Translated by ChatGPT 5