#2165 Finding Dongyi

1 s   128 MB  

Description

선분 위에 갱이와 동이가 있다. 2년간 같이 움직이던 둘은 피치 못할 사정에 의해 떨어져 지내게 되었다. 남은 2년간 같이 밥을 먹을 사람이 필요했던 갱이는 동이를 찾아 나서기로 했다. 이들 발밑에는 숫자가 쓰여 있는 발판이 있는데, 발판에 쓰여 있는 숫자만큼 이동하고, 발판의 숫자가 0인 곳에 동이가 있다. 발판의 숫자가 양수면 오른쪽으로, 음수면 왼쪽으로 움직인다.

끝없는 과제 속에 있는 갱이는 당신에게 동이를 찾기 위해 거쳐 간 발판의 개수와 동이가 있는 위치를 알려주는 프로그램을 만들어달라고 의뢰했다. 아직까지 과제 속에서 헤엄칠 불쌍한 갱이를 위해 프로그램을 만들어주자. 

Finding Dongyi 그림 설명

위 그림은 예제의 두 번째 케이스를 나타낸 그림이다. 처음 갱이는 가장 왼쪽의 발판 위에 서있다. [0]번 발판의 숫자가 3이므로 오른쪽으로 세 칸 움직여 [3]번 발판 위에 도착한다. 그 다음 [3]번 발판의 숫자는 1이므로 오른쪽으로 한 칸 움직여 [4]번 발판 위에 도착한다. [4]번 발판의 숫자는 -2이므로 왼쪽으로 두 칸 움직여 0이 쓰여진 [2]번 발판 위에 도착한다. 0이 쓰여진 곳은 동이가 있는 곳이기 때문에 갱이는 더 이상 이동하지 않는다. 이 경우, 갱이가 움직인 총 횟수는 3번이고 동이가 있는 위치는 [2]번 발판이기 때문에 답은 “3 2”를 출력하면 된다. 

Input

첫 줄에 테스트케이스 T (1 ≦ T ≦ 100)가 들어온다.
각 케이스의 첫 번째 줄에는 수직선의 길이 N (3 ≦ N ≦ 1000) 이 들어오고 그 다음 줄에는 N 개의 발판 숫자들이 들어온다. 갱이는 항상 수직선의 첫 번째 발판에서 출발한다. 발판의 index는 0부터 시작해서 N-1로 끝난다. 

Output

갱이가 거쳐 가야 할 발판의 개수와 동이가 있는 위치를 공백을 사이에 두고 차례로 출력하라. 만약 갱이가 수직선 밖으로 나가게 되거나 거쳐 간 발판의 개수가 2*N이 넘는다면 “-1 –1” (큰따옴표 제외) 를 출력한다. 

Sample Input

Sample Output

3
5
0 1 2 3 4
5
3 -1 0 1 -2 5
5 1 1 1 0
0 0
3 2
-1 -1

Source

2014 Ajou Programming Contest, Division 1∙2