hanzch   2년 전

Bike Tour (자전거 투어)

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
10초 1024 MB



문제

Li는 스위스 산맥을 통과하는 자전거 투어를 계획했습니다. 그의 투어는 N개의 체크포인트로 구성되어 있으며, 방문할 순서대로 1부터 N까지 번호가 매겨져 있습니다. i번째 체크포인트의 높이는 Hi입니다.

체크포인트가 봉우리(peak)가 되는 조건은 다음과 같습니다:

  • 첫 번째 체크포인트도 아니고 N번째 체크포인트도 아니어야 함
  • 해당 체크포인트의 높이가 바로 이전 체크포인트와 바로 다음 체크포인트의 높이보다 엄격히 더 높아야 함

Li가 봉우리의 개수를 찾을 수 있도록 도와주세요.

입력

첫 줄에는 테스트 케이스의 개수 T가 주어집니다. 이어서 T개의 테스트 케이스가 따릅니다. 각 테스트 케이스는 정수 N을 포함한 한 줄로 시작합니다. 두 번째 줄에는 N개의 정수가 주어지며, i번째 정수는 Hi입니다.

출력

각 테스트 케이스에 대해 `Case #x: y` 형식으로 한 줄을 출력합니다. 여기서 `x`는 테스트 케이스 번호(1부터 시작)이고 `y`는 Li의 자전거 투어에서 봉우리의 개수입니다.

제한

  • 1 ≤ T ≤ 100
  • 1 ≤ Hi ≤ 100

테스트 세트 1 (5점)

  • 3 ≤ N ≤ 5

테스트 세트 2 (7점)

  • 3 ≤ N ≤ 100

예제

예제 입력 1

4
3
10 20 14
4
7 7 7 7
5
10 90 20 90 10
3
10 3 10
복사

예제 출력 1

Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 0
복사

힌트

  • 예제 1번에서는 2번째 체크포인트가 봉우리입니다.
  • 예제 2번에서는 봉우리가 없습니다.
  • 예제 3번에서는 2번째와 4번째 체크포인트가 봉우리입니다.
  • 예제 4번에서는 봉우리가 없습니다.

댓글을 작성하려면 로그인해야 합니다.