Islands in the Data Stream#6387
Given a sequence of integers a_1, a_2, a_3, ..., a_n, an island in the sequence is a contiguous subsequence for which each element is greater than the elements immediately before and after the subsequence. In the examples below, each island in the sequence has a bracket below it. The bracket for an island contained within another island is below the bracket of the containing island.
Write a program that takes as input a sequence of non-negative integers, in which each integer differs from the previous integer by at most , and outputs the number of islands in the sequence.
The first line contains the number of data sets p~(1 \le p \le 1000) that follow. Each data set should be processed identically and independently.
Each data set consists of a single line. It contains the data set number , followed by non-negative integers separated by a single space. The first and last integers in the sequence will be . Each integer will differ from the previous integer by at most .
For each data set print a line that consists of the data set number , followed by a single space followed by the number of islands in the sequence.
Example 1