구획 말뚝

당신은 방금 길이가 K킬로미터인 토지를 하나 샀다. 이 토지는 매우 좁으므로, 이 문제에서는 고도가 달라지면서 서쪽에서 동쪽으로 이어지는 꺾은선으로 간주한다. 당신은 일정한 간격으로 배치된 K + 1개의 측정 지점 $M_{0}$, $M_{1}$, ..., $M_{K}$에서 토지의 고도(미터 단위)를 알고 있다. 이 지점들은 서쪽 끝에서 각각 0, 1, ..., K km 떨어져 있다.

이 지역에서는 나무 말뚝 하나가 서로 인접한 두 토지 구획의 경계를 나타낸다. 나무 말뚝은 측정 지점에만 세울 수 있으며, 각 지점에는 최대 하나의 말뚝만 세울 수 있다. 현재 말뚝은 두 개 있다. 하나는 0 km 지점에 있고, 다른 하나는 K km 지점에 있다. 말뚝이 있는 측정 지점은 그 말뚝이 구분하는 두 구획 모두의 일부로 간주되므로, 당신의 토지는 0 km부터 K km까지의 모든 측정 지점을 양 끝점까지 포함한다.

어떤 구획에 측정 지점 세 개가 존재하여, 그 세 지점 중 가장 서쪽과 가장 동쪽에 있는 지점이 나머지 한 지점보다 둘 다 엄격히 높거나, 둘 다 엄격히 낮으면 그 구획은 매력적이라고 간주한다. 사람들은 풍경에 어느 정도 변화가 있는 것을 좋아한다! 이 세 지점은 반드시 연속할 필요가 없으며, 세 지점 중 가장 서쪽과 가장 동쪽에 있는 지점이 반드시 해당 구획에서 가장 서쪽과 가장 동쪽에 있는 지점일 필요도 없다.

K = 5이고 $M_{0}$, $M_{1}$, ..., $M_{K}$ = 5, 6, 6, 1, 2, 4인 예를 생각해 보자. 고도가 5, 2, 4인 측정 지점들은 조건을 만족하며, 고도가 6, 1, 2인 측정 지점들도 조건을 만족한다. 하지만 고도가 6, 6, 1인 측정 지점들은 조건을 만족하지 않으며, 고도가 1, 2, 4인 측정 지점들도 조건을 만족하지 않는다. 조건을 만족하는 측정 지점 세 개가 하나라도 있으면 구획 전체가 매력적이 된다. 예를 들어 측정 지점 4 7 6 7을 포함하는 구획은 처음 세 값 때문에 매력적이다.

당신의 구획은 매력적이지만, 여기서 더 많은 가치를 끌어낼 수 있을지도 모른다고 생각한다! 이 구획에 말뚝을 추가하여 여러 구획으로 나누고 싶으며, 토지를 조금도 낭비하고 싶지 않으므로 모든 구획이 매력적이어야 한다. 추가할 수 있는 말뚝 수의 최댓값은 얼마인가?

제한

시간 제한: 테스트 세트당 20초. (테스트 실행당 10초.) 메모리 제한: 1GB. 1 ≤ T ≤ 100. 모든 i에 대해 0 ≤ $M_{i}$ ≤ 1000. 어떤 i < j < k에 대해 ($M_{i}$ - $M_{j}$) × ($M_{k}$ - $M_{j}$) > 0. (시작 구획은 매력적이다.)

테스트 세트 1 (공개)

4 ≤ K ≤ 10.

테스트 세트 2 (비공개)

4 ≤ K ≤ 1000.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 토지 구획의 길이를 킬로미터 단위로 나타내는 정수 K가 담긴 한 줄로 시작한다. 그다음 줄에는 K + 1개의 정수 $M_{0}$, $M_{1}$, ..., $M_{k}$이 주어진다. 여기서 $M_{i}$는 토지의 서쪽 끝에서 i km 떨어진 측정 지점의 고도(미터 단위)이다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 설명한 대로 추가할 수 있는 말뚝 수의 가능한 최댓값이다.

예제 케이스 #1에서는 2 km에 말뚝 하나를 추가하여 총 두 개의 매력적인 구획을 만들 수 있다. 0 km부터 2 km까지의 구획은 4 < 8이고 8 > 7이므로 매력적이다. 2 km부터 4 km까지의 구획은 7 > 3이고 3 < 5이므로 매력적이다.

예제 케이스 #2에서는 다른 말뚝을 추가할 방법이 없다. 1 km 또는 3 km에 말뚝 하나를 추가하면 구획 중 하나에는 측정 지점이 두 개만 포함되어 매력적일 수 없다. 2 km에 말뚝 하나를 추가하면 0 km와 2 km 사이의 구획은 매력적이지만, 2 km와 4 km 사이의 구획은 매력적이지 않다.

예제 케이스 #3에서는 3 km와 5 km에 말뚝을 추가할 수 있다.

예제 케이스 #4에서는 2 km에 말뚝 하나를 추가할 수 있다. 2 km부터 6 km까지의 구획은 10 > 9이고 9 < 12이므로 매력적이라는 점에 유의하라. 하지만 두 번째 말뚝을 추가할 방법은 없다.