악보는 거들 뿐

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

• 음 하나를 연주해야 할 때마다 $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$의 최솟값을 출력한다.