Parcel Posts

You just bought a strip of land that is $K$ kilometres long. It is so narrow that we treat it as a polyline running from west to east, varying only in elevation. You know the elevation of the land, in metres, at $K+1$ evenly spaced measurement marks $M_0, M_1, \dots, M_K$, which sit $0, 1, \dots, K$ km from the western end.

In this region a wooden post marks the boundary between two adjacent parcels. Posts can be placed at measurement marks only, and each mark holds at most one post. Right now there are two posts, one at the 0 km mark and one at the $K$ km mark. A mark with a post belongs to both parcels it separates, so your parcel contains every measurement mark from 0 km to $K$ km.

A parcel is desirable if it contains three measurement marks such that the west-most and the east-most of the three are both strictly higher than the remaining one, or both strictly lower than the remaining one. People like some variation in their land. The three marks need not be adjacent, and the west-most and east-most of the three need not be the ends of the parcel.

Take $K = 5$ with $M_0, M_1, \dots, M_K$ equal to 5, 6, 6, 1, 2, 4. The marks with elevations 5, 2, 4 satisfy the condition, and so do the marks with elevations 6, 1, 2. The marks with elevations 6, 6, 1 do not, and neither do the marks with elevations 1, 2, 4. One satisfying triple is enough to make the whole parcel desirable. For example, a parcel whose marks read 4, 7, 6, 7 is desirable because of the first three values.

Your parcel is desirable, but you think you can get more out of it. You want to add posts to split the land into several parcels, and every one of them must be desirable because you do not want to waste any land. What is the largest number of posts you can add?

The first line contains the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains one integer $K$, the length of your land in kilometres. The second line contains $K+1$ integers $M_0, M_1, \dots, M_K$ separated by spaces, where $M_i$ is the elevation in metres at the mark that is $i$ km from the western end.

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the largest number of posts you can add.

• $1 \le T \le 100$
• $2 \le K \le 10^5$
• The sum of $K$ over all test cases is at most $10^5$.
• $0 \le M_i \le 1000$ for every $i$.
• $(M_i - M_j) \times (M_k - M_j) > 0$ for some $i < j < k$, so the land you bought is desirable.

In the first test case of the sample you can add one post at 2 km and get two desirable parcels. The parcel from 0 km to 2 km is desirable because $4 < 8$ and $8 > 7$. The parcel from 2 km to 4 km is desirable because $7 > 3$ and $3 < 5$.

In the second test case there is no way to add a post. A post at 1 km or at 3 km leaves a parcel with only two measurement marks, which can never be desirable. A post at 2 km makes the parcel from 0 km to 2 km desirable, but the parcel from 2 km to 4 km is not.

In the third test case posts can be added at 3 km and at 5 km.

In the fourth test case a post can be added at 2 km. The parcel from 2 km to 6 km is desirable because $10 > 9$ and $9 < 12$. There is no way to add a second post.