Missile Defense Systems

Country R has upgraded its missile defense system to counter threats from neighboring malicious countries. The new system can shoot down a series of missiles as long as the intercepted missiles come in strictly ascending order by altitude or strictly descending order by altitude. In other words, a missile defense system can successfully intercept a sequence \(a_1, a_2, \dots, a_k\) if either:

\(a_1 < a_2 < \cdots a_2 > \cdots > a_k\).

Given the heights of a sequence of incoming missiles, determine the minimum number of missile defense systems required to bring down all the missiles. Note that a missile defense system can only be used for one sequence (either ascending or descending) and the missiles must be intercepted in the order they arrive.

inputFormat

The first line contains a single integer \(n\) denoting the number of missiles.

The second line contains \(n\) space-separated integers representing the altitudes of the missiles in the order they appear.

\(1 \leq n \leq 10^5\); each altitude is an integer.

outputFormat

Output a single integer representing the minimum number of missile defense systems required to intercept all missiles.

sample

5
1 2 3 4 5

1