악보는 거들 뿐

키위새는 피아노를 잘 치고 싶었지만 악보를 읽을 줄 몰랐다. 그러다 동영상 사이트에서 수열만 보고 피아노를 연주하는 영상을 찾아냈다! 그런데 영상이 보여주는 수에 맞춰 음을 누르니 곡이 제대로 연주되지 않았다. 결국 키위새는 악보 보는 법을 배웠고, 영상이 음을 어떤 원리로 수열에 담았는지 알게 되었다.

• 음 하나를 연주해야 할 때마다 $1$부터 양의 정수 $N$까지의 정수 중 하나를 쓴다.
• 직전에 연주한 음이 현재 연주할 음보다 낮으면 직전에 쓴 수보다 큰 수를 쓴다.
• 직전에 연주한 음이 현재 연주할 음보다 높으면 직전에 쓴 수보다 작은 수를 쓴다.
• 직전에 연주한 음과 현재 연주할 음이 같으면 직전에 쓴 수를 쓴다.

악보 읽기의 달인이 된 키위새는 주어진 악보를 위 규칙에 따라 수열로 옮겨 동영상 사이트에 피아노 연주 영상을 올리기로 했다. $N$이 클수록 연주할 음의 종류가 많아지므로 사람들이 영상을 어렵게 느낄 수 있다. 사람들이 어렵게 느끼지 않도록 $N$의 최솟값을 찾아주자.

첫째 줄에 악보에서 연주해야 할 음의 개수 $M$이 주어진다. $(1 \leq M \leq 500\,000)$

둘째 줄에 악보에 쓰인 음의 높이를 나타내는 정수 $p_1$, $p_2$, $\cdots$, $p_M$이 공백으로 구분되어 주어진다. $(1 \leq p_i \leq 10^9)$

악보의 각 음은 연주할 순서대로 주어지며, 한 번에 둘 이상의 음을 연주하는 경우는 없다.

첫째 줄에 $N$의 최솟값을 출력한다.