음악 루프의 피크

시간 제한2초메모리 제한512 MB

요약

인접한 값이 모두 다르고 처음과 끝도 다른 순환 수열에서 극댓값과 극솟값의 개수를 센다.

난이도: 쉬움10점 중 3점
유형: 구현, 배열, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

음악 루프는 끝에 도달하면 처음부터 다시 시작하도록 작곡한 음악 조각이다. 이어 붙인 자리에서 끊김이 들리지 않는다. 루프는 게임 사운드, 특히 웹 캐주얼 게임에서 많이 쓴다.

루프는 예를 들어 PCM으로 디지털화한다. PCM(Pulse Code Modulation)은 아날로그 신호를 표현하는 기법이고, 디지털 오디오에서 널리 쓴다. 이 기법은 일정한 시간 간격으로 신호의 크기를 표본화하고 표본값을 순서대로 저장한다. 표본화한 파형을 재생할 때는 이 과정을 거꾸로 돌린다(복조).

페르난다는 게임을 만드는 회사에서 일하며, 음악 루프를 하나 작곡해 PCM으로 부호화했다. 오디오 편집 프로그램에서 자기 루프의 파형을 살펴보다가 피크가 몇 개인지 세어 보고 싶어졌다. 파형의 피크는 국소 최대 또는 국소 최소가 되는 표본값, 즉 파형이 방향을 바꾸는 지점이다. 아래 그림은 (a) 파형의 예와 (b) 그 파형으로 만든 루프를 보여 준다. (b)의 루프에는 피크가 48개 있다.

페르난다의 음악 루프에 피크가 몇 개 있는지 구하라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 루프의 표본 개수를 나타내는 정수 $N$ 이 주어진다 ( $2 \le N \le 10^4$ ). 둘째 줄에는 표본의 크기를 나타내는 정수 $H_1, H_2, \dots, H_N$ 이 공백으로 구분되어 주어진다 ( $-10^4 \le H_i \le 10^4$ , $H_1 \ne H_N$ , $1 \le i < N$ 인 모든 $i$ 에 대해 $H_i \ne H_{i+1}$ ). 루프를 재생하면 $H_N$ 다음에 $H_1$ 이 이어진다.

입력의 끝은 0 하나만 있는 줄로 나타낸다.

출력

각 테스트 케이스마다 페르난다의 음악 루프에 있는 피크의 개수를 정수 하나로 한 줄에 출력한다.

예제5

예제 1

입력

2
1 -3
6
40 0 -41 0 41 42
4
300 450 449 450
0

예상 출력

2
2
4

예제 2
입력
```
2
5 7
0
```
예상 출력
```
2
```
예제 3
입력
```
2
-10000 10000
0
```
예상 출력
```
2
```
예제 4
입력
```
5
1 2 3 4 5
0
```
예상 출력
```
2
```
예제 5
입력
```
6
1 -1 1 -1 1 -1
0
```
예상 출력
```
6
```