필지 경계 말뚝

동서로 길게 뻗은 땅을 샀다. 이 땅의 길이는 $K$ 킬로미터이고 폭이 아주 좁아서, 서쪽 끝에서 동쪽 끝으로 이어지며 높이만 변하는 꺾은선으로 본다. 서쪽 끝에서 각각 $0, 1, \dots, K$ km 떨어진 $K+1$개의 측정점 $M_0, M_1, \dots, M_K$에서 땅의 높이를 미터 단위로 알고 있다.

이 지역에서는 나무 말뚝이 이웃한 두 필지의 경계를 나타낸다. 말뚝은 측정점에만 세울 수 있고, 한 측정점에는 말뚝을 하나까지만 세울 수 있다. 지금 말뚝은 두 개다. 하나는 0 km 지점에, 다른 하나는 $K$ km 지점에 있다. 말뚝이 선 측정점은 그 말뚝이 갈라놓는 두 필지에 모두 속한다고 본다. 그래서 내 땅에는 0 km부터 $K$ km까지의 모든 측정점이 들어간다.

어떤 필지 안에 측정점 세 개가 있고, 그중 가장 서쪽 것과 가장 동쪽 것이 모두 나머지 하나보다 높거나 모두 나머지 하나보다 낮으면, 그 필지를 좋은 필지라고 한다. 사람들은 땅의 높낮이가 조금은 변하는 쪽을 좋아한다. 이 세 측정점이 서로 이웃해야 하는 것은 아니고, 그중 가장 서쪽 것과 가장 동쪽 것이 필지의 양 끝일 필요도 없다.

$K = 5$이고 $M_0, M_1, \dots, M_K$가 5, 6, 6, 1, 2, 4인 경우를 보자. 높이가 5, 2, 4인 측정점 세 개는 조건을 만족하고, 높이가 6, 1, 2인 세 개도 조건을 만족한다. 반면 높이가 6, 6, 1인 세 개는 조건을 만족하지 않고, 높이가 1, 2, 4인 세 개도 만족하지 않는다. 조건을 만족하는 측정점 세 개가 하나라도 있으면 그 필지 전체가 좋은 필지다. 예를 들어 측정점의 높이가 4, 7, 6, 7인 필지는 앞의 세 값 때문에 좋은 필지다.

내 땅은 이미 좋은 필지지만, 여기서 값을 더 끌어낼 수 있을 것 같다. 말뚝을 더 세워 이 땅을 여러 필지로 나누려고 한다. 땅을 한 조각도 버리고 싶지 않으니 나뉜 필지는 모두 좋은 필지여야 한다. 말뚝을 최대 몇 개까지 더 세울 수 있는가?

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에는 땅의 길이 $K$가 킬로미터 단위의 정수로 주어진다. 둘째 줄에는 $K+1$개의 정수 $M_0, M_1, \dots, M_K$가 공백으로 구분되어 주어진다. $M_i$는 서쪽 끝에서 $i$ km 떨어진 측정점의 높이이고, 단위는 미터다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 더 세울 수 있는 말뚝의 최대 개수다.

• $1 \le T \le 100$
• $2 \le K \le 10^5$
• 모든 테스트 케이스의 $K$를 더한 값은 $10^5$ 이하다.
• 모든 $i$에 대해 $0 \le M_i \le 1000$
• 어떤 $i < j < k$에 대해 $(M_i - M_j) \times (M_k - M_j) > 0$이다. 즉 처음 산 땅은 좋은 필지다.

예제의 첫째 테스트 케이스에서는 2 km 지점에 말뚝 하나를 세워 좋은 필지 두 개를 만들 수 있다. 0 km에서 2 km까지의 필지는 $4 < 8$이고 $8 > 7$이므로 좋은 필지다. 2 km에서 4 km까지의 필지는 $7 > 3$이고 $3 < 5$이므로 좋은 필지다.

둘째 테스트 케이스에서는 말뚝을 더 세울 방법이 없다. 1 km나 3 km에 세우면 한쪽 필지에 측정점이 두 개만 들어가서 좋은 필지가 될 수 없다. 2 km에 세우면 0 km에서 2 km까지는 좋은 필지가 되지만 2 km에서 4 km까지는 좋은 필지가 아니다.

셋째 테스트 케이스에서는 3 km와 5 km에 말뚝을 세울 수 있다.

넷째 테스트 케이스에서는 2 km에 말뚝을 세울 수 있다. 2 km에서 6 km까지의 필지는 $10 > 9$이고 $9 < 12$이므로 좋은 필지다. 그러나 말뚝을 두 개 세울 방법은 없다.