점프하는 요시

요시는 개구리다. 동물원의 통나무 밑에 사는데, 이 통나무는 먼 적도 우림에서 통째로 옮겨 온 것이다. 크고 축축해서 파리가 잘 꼬이고, 요시는 그 점이 마음에 든다.

통나무 앞 습지에는 조약돌이 일렬로 놓여 있다. 조약돌마다 검은 반점이 있어서, 요시는 가끔 그 반점을 아주 큰 파리라고 상상하며 바라본다.

어제는 친구인 낙타 아다우저가 찾아와 놀이를 하나 제안했다.

"저 조약돌의 반점이 보이지? 맨 왼쪽 조약돌에서 출발해서 조약돌 사이를 뛰어 봐. 규칙이 하나 있어. 두 조약돌의 반점 수를 더한 값이 두 조약돌 사이의 거리와 같을 때만 그 둘 사이를 뛸 수 있어. 그리고 최대한 멀리 있는 조약돌까지 가야 해."

"좋아. 그런데 나는 스물셋까지밖에 못 세는데." 요시가 망설였다.

"큰 수는 내가 세어 줄게." 아다우저가 답했다.

조약돌은 일직선으로 놓여 있고, 이웃한 두 조약돌 사이의 거리는 정확히 $1$이다. 뛰는 방향은 왼쪽이든 오른쪽이든 상관없다. 첫 번째 조약돌에서 출발해 규칙에 맞는 점프를 여러 번 반복해서 도달할 수 있는 조약돌 중, 첫 번째 조약돌에서 가장 먼 것의 거리를 구하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 조약돌의 개수 $N$ ($1 \le N \le 10^6$)이 주어진다. 둘째 줄에는 정수 $N$개가 조약돌이 놓인 순서대로 주어지며, $i$번째 정수는 $i$번째 조약돌의 반점 수다. 반점 수는 $0$ 이상 $10^9$ 이하다. 요시가 뛸 수 있는 서로 다른 조약돌 쌍의 개수는 $10^6$개를 넘지 않는다.

입력의 마지막 줄에는 $0$ 하나만 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 규칙에 맞는 점프를 반복해서 도달할 수 있는 조약돌 중 첫 번째 조약돌에서 가장 먼 것의 거리를 한 줄에 하나씩 출력한다. 첫 번째 조약돌에서 한 번도 뛸 수 없으면 $0$을 출력한다.