장난감 묶음 할인

Albert는 그 동안 모은 n개의 오래된 장난감을 모두 팔아버리기로 했다. 편의상 장난감은 0부터 n-1까지 번호가 붙어있고, i번 장난감의 판매가격은 v[i] 이다. Albert는 한 명의 구매자에게 모든 장난감을 팔아버리고 새로운 장난감을 사고 싶어 하는데, 마침 Alice가 소식을 듣고 모든 장난감을 구매하기로 했다. Alice가 모든 장난감을 사는 대신, 아래와 같은 "묶음 할인"을 받을 수 있도록 요청했다:

• Alice가 임의로 i번 장난감부터 i+(3k-1)번까지 연속한 3k개의 장난감을 묶어서 구입하면, 3k개의 장난감 중 가장 비싼 k개의 가격만큼 할인 해준다 (Alice는 이를 "k-묶음 할인" 이라 부른다).
• 단, 하나의 장난감은 최대 한 번만 "묶음"에 속할 수 있고, 각 묶음은 반드시 연속한 번호로 구성된 3k개의 장난감 이어야 한다.
• Alice는 묶음 할인을 여러 번 받을 수 있고, 각 묶음에 포함된 장난감의 개수는 제각기 다를 수 있다 (3의 배수이기만 하면 된다).
• Alice가 원하는 만큼 임의로 k-묶음 할인을 적용하여 할인된 가격에 장난감을 산 후, 만약 더 이상 묶음 할인을 받을 수 없게 되면 남은 장난감들은 각각의 판매 가격에 구매하기로 했다.

항상 Alice의 술수에 손해를 보는 Albert이지만, 장난감을 모두 팔기위해 Alice의 제안을 승낙하는 대신 조건을 하나 추가했다. n개의 장난감 중 번호가 3의 배수인 것 중 하나를 Albert가 임의로 고르면 Alice는 해당 장난감은 판매 가격 그대로 사야하며, 대신 나머지 장난감들에 대해 원하는대로 묶음 할인을 적용할 수 있게 했다. Alice도 잠시 고민을 한 후, 제안을 받아들이기로 했다.

예를 들어, n = 7이고 v = [1 2 3 100 10 20 30] 이라고 하자.

• Albert가 먼저 임의로 0번, 3번, 6번 장난감 중 하나를 골라 Alice에게 팔 수 있다.
• 만약 0번 장난감을 (가격 1에) 판다면, Alice는 (1번,2번,3번)을 묶어 (2+3)을 지불하고 (4번,5번,6번)을 묶어 (10+20)을 지불하여 총 36을 지불하고 장난감을 모두 살 수 있다.
• 만약 3번 장난감을 (가격 100에) 판다면, Alice는 0-2번과 4-6번 장난감을 각각 묶어 총 100 + (1 + 2) + (10 + 20) = 133을 지불하고 장난감을 모두 살 수 있다.
• 만약 6번 장난감을 (가격 30에) 판다면, Alice는 0번부터 5번 모두를 묶어 총 30 + (1+2+3+10) = 46을 지불하고 장난감을 모두 살 수 있다.

모든 경우를 따져보면, Albert는 당연히 3번 장난감을 팔아야 하고, 이 때 Alice도 최선을 다해 최소한의 가격을 지불하려 한다면 133을 지불하게 된다.

Alice는 항상 꼼꼼하게 모든 경우를 따져보기 때문에, Albert는 당신에게 도움을 요청했다.

입력으로 n과 v가 주어졌을 때, Albert가 어떤 장난감 하나를 임의로 골라 Alice에 팔아야 최대한 많은 돈을 받을 수 있는지 구해보자.

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

각 테스트 케이스는 두 줄에 걸쳐 주어진다.

테스트 케이스의 첫 줄에 n이 주어지며 (장난감의 수) 둘째 줄에 n개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 나타내는 정수 두 개를 공백으로 구분하여 각 줄에 출력한다.

첫 수는 Albert가 처음 팔아야하는 장난감의 번호이고 (0이상 n-1이하), 두 번째 수는 이 때 Alice가 지불해야하는 총 금액이다.

총 금액이 같은 답이 여럿 존재하는 경우, 장난감의 번호가 가장 작은 경우를 출력한다.

• 1 ≤ T ≤ 15
• 4 ≤ n < 30,000 (단, n을 3으로 나눈 나머지가 1인 n만 입력으로 주어진다)
• 1 ≤ v[i] ≤ 1,000,000,000 (1 ≤ i ≤ n)