33619번 - 햄부기 스페셜 저지

문제

피돌이들이 화가 나 있다! 피돌이들은 총 $N$명 있으며 1번부터 $N$번까지의 번호가 붙어있다. $i$번 피돌이가 화난 정도는 정수 $a_i$로 나타낼 수 있다. 이는 $i$번 피돌이가 햄부기 $a_i$개 만큼 화났음을 의미하며 이는 햄부기를 1개 받을 때마다 1씩 줄어든다. $a_i=0$이라면 $i$번 피돌이가 화나 있지 않음을 나타낸다.

당신은 피돌이들에게 햄부기를 뿌려 피돌이들을 진정시키려고 한다. 하지만 햄부기를 그냥 뿌리는 것은 재미없다고 생각한 당신은 다음과 같은 방식을 사용하기로 했다.

• 현재 상태에서 화가 나 있는 피돌이들의 수를 $p,ドル 화가 나 있는 피돌이 중 번호가 $x$번째로 작은 피돌이의 번호를 $f(x)$라고 하자. 1ドル \leq i < p$인 정수 $i$를 골라 $f(i)$번 피돌이와 $f(i+1)$번 피돌이에게 햄부기를 $\min(a_{f(i)}, a_{f(i+1)})$개 만큼 준다.

당신은 위의 방법대로 햄부기를 뿌려 피돌이들이 화난 정도의 합 $k$를 최소화 하고싶다. $k$의 최솟값과 $k$가 최솟값이 되게하는 방법을 하나 찾아보자. 단, 햄부기는 무한히 있다고 가정한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\leq T \leq 100)$

각 테스트 케이스의 첫째 줄에 피돌이들의 수 $N$이 주어진다. $(2 \leq N \leq 1\ 000)$

각 테스트 케이스의 둘째 줄에 각 피돌이들이 초기에 화난 정도를 나타내는 $N$개의 정수 $a_1, a_2, \cdots, a_N$이 공백을 두고 주어진다. $(1 \leq a_i \leq 100)$

모든 테스트 케이스에서 $N$의 합은 1ドル\ 000$을 넘지 않는다.

출력

각 테스트 케이스의 첫째 줄에 $k$의 최솟값과 햄부기를 주는 횟수 $x$를 공백을 두고 출력한다.

각 테스트 케이스의 둘째 줄에 몇 번째 피돌이에게 햄부기를 줘야 하는지 나타내는 $x$개의 정수 $p_1, p_2, \cdots , p_x$를 공백을 두고 출력한다. $p_i$는 $i$번째로 햄부기를 줄 때 $f(p_i)$번째 피돌이와 $f(p_i+1)$번째 피돌이에게 줬음을 나타낸다.

제한

힌트