낮아진 검사 받침대

문제

한 공장의 생산 라인에는 제품을 잠시 올려 두는 받침대가 일렬로 놓여 있다. 관리자는 각 받침대의 높이를 측정하여 생산 라인의 왼쪽부터 차례대로 기록했다. 받침대에는 왼쪽부터 1번, 2번, …, N번이라는 번호가 붙어 있다. 기록에 적힌 높이는 모두 양의 정수이며, 서로 다른 받침대의 높이가 같을 수도 있다. 관리자는 양옆의 받침대보다 낮은 곳에만 점검 표시를 붙이려고 한다. 어떤 받침대가 점검 대상이 되려면 바로 왼쪽 받침대와 바로 오른쪽 받침대가 모두 있어야 한다. 또한 자신의 높이가 두 이웃의 높이보다 각각 엄격하게 작아야 한다. 두 이웃 중 하나라도 자신과 높이가 같으면 점검 대상이 아니다. 멀리 떨어진 받침대의 높이는 판단에 사용하지 않는다. 예를 들어 세 받침대의 높이가 왼쪽부터 8, 3, 7이라면 가운데 받침대는 점검 대상이다. 반면 높이가 8, 3, 3이라면 가운데 받침대는 오른쪽 이웃과 높이가 같으므로 점검 대상이 아니다. 생산 라인의 맨 왼쪽과 맨 오른쪽은 이웃이 한쪽에만 있으므로 항상 점검 대상에서 제외한다. 받침대가 하나뿐일 때도 점검 대상을 정할 수 없다. 점검 표시를 붙이는 동안 받침대를 옮기거나 높이를 바꾸지는 않는다. 따라서 모든 받침대는 처음 입력된 높이를 기준으로 판단하며, 앞에서 붙인 표시가 뒤의 판단에 영향을 주지 않는다. 여러 받침대가 조건을 만족하면 그 받침대들을 모두 센다. 기록된 높이를 보고 점검 표시를 붙일 받침대의 개수를 구한다. 조건을 만족하는 받침대가 하나도 없으면 개수는 0이다.

입력

첫째 줄에 받침대의 개수 N이 주어진다. 둘째 줄에 왼쪽부터 기록한 높이 H_1, H_2, …, H_N이 공백으로 구분되어 주어진다. 모든 입력값은 정수이며, 1 ≤ N ≤ 1,000, 1 ≤ H_i ≤ 1,000이다.

출력

점검 대상인 받침대의 개수를 정수 하나로 출력한다. 점검 대상이 없으면 0을 출력한다.

7
9 4 8 3 3 7 2

1

5
6 2 7 1 5

2

1
4

0

출처: Devin.KR 자체 제작