1974번 - Jump Jump Championship 스페셜 저지

후연 조교는 2007년 황금 돼지해(확실치 않음)를 맞이하여 Jump Jump Championship에 참가하였다. 이 대회에서는 아래와 같은 규정으로 우승자를 가린다.

우선 점프대가 N개 있는데, 원하는 아무 한 곳 점프대에서 출발하여 오른쪽으로만 진행하면서 점프대에 놓여있는 트로피를 가장 많이 주워야 한다. 단, 트로피를 가져올 때의 조건은 아래와 같다:

1. 첫 점프대의 트로피는 그냥 가져갈 수 있다.
2. 첫 번째 이후 도달하는 점프대에 놓인 트로피를 가져가기 위해서는 이전에 있었던 점프대에서 주워온 트로피를 넣을 수 있어야 한다. 즉 이전에 얻은 트로피의 크기가 더 작아야 한다. 작은 트로피를 넣었으면, 이제 큰 트로피를 들고, 다른 점프대로 이동하여 마찬가지로 반복한다. (혹은 이동할 곳이 없으면 끝난다)
3. 트로피를 가져가지 않으면서 다른 점프대로 이동할 수 없다.

예를 들어 점프대가 5개 있고, 트로피의 크기가 3 2 4 2 5와 같이 놓여 있다면, 2번 점프대 → 3번 점프대 → 5번 점프대로 이동하여 (2 4 5)의 트로피 3개를 얻을 수 있다. 혹은 1번 점프대 → 3번 점프대 → 5번 점프대의 경우도 가능하다.

당신은 후연 조교를 도와서 후연 조교가 최대 몇 개의 트로피를 얻을 수 있는지, 또 어떤 방법으로 얻을 수 있는지 알아내야 한다.

첫 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스에 대해서는 점프대의 수 N(1 ≤ N ≤ 10,000)과 각 점프대에 놓인 트로피들의 크기가 주어진다. 크기가 같은 트로피가 있을 수 있으며 트로피의 1부터 100만 이하의 자연수이다.

각 테스트 케이스에 대해 첫 줄에 후연 조교가 얻을 수 있는 최대 트로피의 수를 출력하고, 둘째 줄에는 이동한 점프대의 경로를 출력한다. 여러 가지가 있을 경우 아무거나 한 가지를 출력한다.