The score is just a helper

Kiwi bird wanted to play the piano well, but could not read sheet music. Then it found a video site with a performance where the piano is played from a sequence of numbers alone! However, when it pressed the keys matching the numbers in the video, the song did not play correctly. In the end, Kiwi bird learned to read sheet music and figured out the rule the video used to turn notes into a sequence.

• Each time a note must be played, write one integer from 1 to a positive integer $N$.
• If the previously played note is lower than the current note, write a number greater than the number written previously.
• If the previously played note is higher than the current note, write a number less than the number written previously.
• If the previously played note is the same as the current note, write the same number as the number written previously.

Having become an expert at reading sheet music, Kiwi bird decided to convert the score into a sequence by these rules and upload a piano performance video to a video site. A larger $N$ means more kinds of notes to play, which can make the video harder for viewers. Find the minimum value of $N$ so that viewers do not find the video difficult.

The first line contains the number of notes $M$ to play in the score. $(1 \leq M \leq 500\,000)$

The second line contains the integers $p_1$, $p_2$, $\cdots$, $p_M$ that represent the pitches of the notes in the score, separated by spaces. $(1 \leq p_i \leq 10^9)$

The notes in the score are given in the order they are played, and no two or more notes are played at the same time.

Print the minimum value of $N$ on the first line.