406050: GYM102222 L Continuous Intervals

Lamis is a smart girl. She is interested in problems about sequences and their intervals.

Here she shows you a sequence of length $$$n$$$ with positive integers, denoted by $$$a_1, a_2, a_3, \cdots, a_n$$$. She is amazed at those intervals, which is a consecutive subsequence of $$$a_1,a_2,\cdots,a_n$$$, with several continuous numbers, and names them continuous intervals.

More precisely, consider a interval $$$a_l,a_{l+1},\cdots,a_{r-1},a_r$$$ for instance where $$$1\le l\le r\le n$$$. If, after sorting the interval, the difference of any two neighbouring items is less than or equal to $$$1$$$, the interval will be considered as continuous.

As her best friends, you came from far and wide and travelled thousands of miles to Ningxia, to help her count the number of continuous intervals of the sequence.

The input contains several test cases, and the first line is a positive integer $$$T$$$ indicating the number of test cases which is up to $$$1000$$$.

For each test case, the first line contains an integer $$$n~(1 \leq n \leq 10^5)$$$ which is the length of the given sequence. The second line contains $$$n$$$ integers describing all items of the sequence, where the $$$i$$$-th one is denoted by $$$a_i~(1 \leq a_i \leq 10^9)$$$.

We guarantee that the sum of $$$n$$$ in all test cases is up to $$$10^6$$$.

For each test case, output a line containing Case #x: y, where x is the test case number starting from $$$1$$$, and y is the number of continuous intervals in this test case.

2
4
1 2 1 2
4
1 3 2 4

Case #1: 10
Case #2: 8