팬케이크 덱

팬케이크는 보통 쌓아서 제공하지만, Infinite House of Pancakes은 변화를 받아들인다! 이 식당의 새로운 광고 전략은 팬케이크를 덱, 즉 양방향 큐에서 제공하는 것이다.

당신은 이 식당의 종업원이며, 덱에 있는 모든 팬케이크를 제공하는 것이 임무이다. 손님들은 한 번에 한 명씩 오며, 각자 팬케이크 하나를 받는다. 각 손님에게 덱의 가장 왼쪽 또는 가장 오른쪽 팬케이크를 제공해야 하며, 어느 쪽을 선택할지는 자유이다. 팬케이크를 제공하면 그 팬케이크는 덱에서 사라지고, 그 옆에 있던 팬케이크가 드러난다. 또는 팬케이크가 하나만 남으면 그 팬케이크를 제공하는 것만이 유일한 선택이며, 그러면 임무가 끝난다!

각 팬케이크에는 맛있음 정도가 있다. 손님은 자신이 받을 팬케이크를 선택할 수 없으므로, 자신이 받은 팬케이크가 이전의 모든 손님이 받은 각각의 팬케이크만큼 맛있는 경우에만 그 팬케이크의 값을 지불하면 된다. (첫 번째 손님의 경우에는 이전 손님이 없으므로 항상 자신의 팬케이크 값을 지불한다.)

그 수가 최대가 되는 순서로 팬케이크를 제공할 때, 몇 명의 손님이 자신의 팬케이크 값을 지불하는가?

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $1 \le \mathbf{D_i} \le 10^6$, 모든 $i$에 대해.

테스트 세트 1 (Visible Verdict)

$2 \le \mathbf{N} \le 20$.

테스트 세트 2 (Visible Verdict)

$2 \le \mathbf{N} \le 100$.

테스트 세트 3 (Hidden Verdict)

$2 \le \mathbf{N} \le 10^5$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 줄로 설명된다. 테스트 케이스의 첫 번째 줄에는 팬케이크 덱에 있는 팬케이크의 수를 나타내는 정수 하나 $\mathbf{N}$가 주어진다. 테스트 케이스의 두 번째 줄에는 $\mathbf{N}$개의 정수 $\mathbf{D_1}, \mathbf{D_2}, \dots, \mathbf{D_N}$가 주어지며, 여기서 $\mathbf{D_i}$는 덱에서 왼쪽부터 $i$번째 팬케이크의 맛있음 정도이다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 1부터 시작하고, $y$는 그 수가 최대가 되는 순서로 팬케이크를 제공할 때 자신의 팬케이크 값을 지불하는 손님의 수이다.

예제 케이스 #1에서는 팬케이크를 제공할 수 있는 순서가 두 가지이다. 맛있음 정도가 $5$인 팬케이크를 먼저 제공하면 그 팬케이크 하나만 값이 지불된다. 맛있음 정도가 $1$인 팬케이크를 먼저 제공하면 둘 다 값이 지불된다.

예제 케이스 #2는 문제 설명에 나온 그림이다. 다음은 팬케이크를 제공할 수 있는 순서를 맛있음 정도로 나타낸 것이다. 밑줄이 그어진 팬케이크는 손님이 값을 지불하는 팬케이크이다.

• $\underline{1}, \underline{4}, 2, 3$

• $\underline{1}, \underline{4}, 3, 2$

• $\underline{1}, \underline{3}, \underline{4}, 2$

• $\underline{1}, \underline{3}, 2, \underline{4}$

• $\underline{3}, 1, \underline{4}, 2$

• $\underline{3}, 1, 2, \underline{4}$

• $\underline{3}, 2, 1, \underline{4}$

• $\underline{3}, 2, \underline{4}, 1$

보다시피 $3$개의 팬케이크 값이 지불되는 순서가 몇 가지 있지만, $4$개 모두의 값이 지불되는 순서는 없다.

예제 케이스 #3에서는 제공 순서와 관계없이 모든 팬케이크의 값이 지불된다.

예제 케이스 #4에서는 어느 팬케이크를 먼저 제공하더라도 가운데의 두 팬케이크는 절대 값이 지불되지 않는다. 할 수 있는 최선은 맛있음 정도가 7인 팬케이크를 맛있음 정도가 1000000인 팬케이크보다 먼저 제공하는 것이다.