지구 온난화 Batch 컴파일 명령

과학자인 승현이는 높아지는 해수면이 풍경을 어떻게 바꾸는지 연구하고 싶습니다. 특히, 이 해수면이 섬의 개수를 어떻게 바꾸는지 알고자 합니다. 그는 우선 1차원 세상을 연구합니다. 1차원 세상은 음이 아닌 정수들로 구성된 수열 $h_{0}, h_{1}, \cdots, h_{n-1}$로 표현됩니다. 각 $h_{i}$는 좌표 $i$의 고도를 의미합니다. 다음 그림은 수열 $5,6,1,3,2,9,8$로 표현된 세상을 표현한 것입니다.

지금 만약 해수면이 고도 2.5에 있다면, 첫 두 개의 열, 4번째 열, 그리고 마지막 두 개의 열로 구성된 3개의 섬이 있습니다. 더욱이, 만약 해수면이 고도 3.5에 있다면, 섬이 두 개밖에 없을 것입니다. 해수면이 고도 $x$에 있다면, 고도가 $x$에 있는 대륙은 바다 밑으로 가라앉았다고 가정합니다. 따라서, 만약 해수면이 고도 3에 있다면, 2개의 섬이 있는 것입니다. 참고로 모든 가능한 해수면의 높이에 대해 섬은 최대 3개까지만 생길 수 있습니다.

1차원 세상에 대한 정보가 주어질 때, 승현이는 모든 가능한 해수면의 높이에 대해 만들어질 수 있는 섬이 최대 몇 개인지 알고자 합니다.

입력 형식

첫 번째 줄에 수열의 길이 $n$이 주어집니다. 다음 $n$개 줄에는 수열의 각 원소 $h_{0}, h_{1}, \cdots, h_{n-1}$이 순서대로 주어집니다. 수열의 각 원소는 음이 아니며 $2^{30}$보다 작습니다.

출력 형식

첫 번째 줄에 섬의 최대 개수를 출력합니다.

서브태스크

각 입력에 대해 실행 시간 제한은 1.0초입니다. 여러분이 제출한 코드는 아래 입력 조건에 따라 평가될 것입니다.

1. (6점) $N \le 1,000.$
2. (6점) $N \le 100,000.$ 각 위치의 고도는 최대 20입니다.
3. (7점) $N \le 100,000.$ 추가적으로, 각 위치의 고도는 서로 다릅니다.
4. (10점) $N \le 1,000,000.$ 각 위치의 고도는 서로 다릅니다.
5. (11점) $N \le 1,000,000.$

예제