Under construction

Still being built. Things may change

Record Breaker

Interview

Time limit20sMemory limit1024 MB

Summary
Count days whose visitor count beats every earlier day and also beats the next day, with the last day allowed to skip the next-day check.
Level

Easy3 of 10

Topics
Array, Implementation, Greedy
Solved
No attempts yet

Problem

Isyana is given the number of visitors at her local theme park on N consecutive days. The number of visitors on the i-th day is Vi. A day is record breaking if it satisfies both of the following conditions:

  • The number of visitors on the day is strictly larger than the number of visitors on each of the previous days.
  • Either it is the last day, or the number of visitors on the day is strictly larger than the number of visitors on the following day.

The very first day could be a record breaking day.

Help Isyana find the number of record breaking days.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The second line contains N integers. The i-th integer is Vi.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of record breaking days.

Limits

  • 1 ≤ T ≤ 100.
  • 0 ≤ Vi ≤ 2 × 105.

Hint

In Sample Case #1, the bold and underlined numbers in the following represent the record breaking days: 1 2 0 7 2 0 2 0.

In Sample Case #2, only the last day is a record breaking day.

In Sample Case #3, the first, the third, and the sixth days are record breaking days.

In Sample Case #4, there is no record breaking day.

Examples1

  1. Example 1

    Input
    4
8
1 2 0 7 2 0 2 0
6
4 8 15 16 23 42
9
3 1 4 1 5 9 2 6 5
6
9 9 9 9 9 9
    Expected output
    Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0