건덕이는 학교에 가기 너무 싫은 나머지 최대한 늦게 학교에 도착하려고 한다. 등굣길은 $N$개의 칸이 가로로 놓인 형태이며, 각 칸은 가장 왼쪽 칸부터 오른쪽으로 $1$부터 $N$까지 번호가 매겨진다. 건덕이는 $1$번 칸에, 학교는 $N$번 칸에 존재한다.</p>

건덕이는 처음에 학교를 바라보는 방향으로 서 있다. 등교하는 방법은 특이한데, $1$분마다 현재 자신이 서 있는 칸에 쓰인 수만큼 바라보는 방향으로 이동한다. 이때, 등굣길을 벗어나도록 이동할 수 없다.

건덕이는 바라보는 방향을 최대 두 번 반전할 수 있다. 학교가 있는 칸에 처음으로 도착하는 시간을 최대한 늦추면 출발 몇 분 뒤에 도착할까? 건덕이가 방향을 반전하는 데 드는 시간은 무시한다.

입력 형식

첫 번째 줄에 학교가 있는 칸의 번호 $N$이 주어진다. $\left( 3\leq N\leq 200\, 000 \right)$</p>

두 번째 줄에 각 칸에 쓰인 정수 $a_i$가 공백으로 구분되어 주어진다. $\left( 0\leq a_i\leq 200\ 000 \right)$

출력 형식

건덕이가 최대한 시간을 끈 뒤, 학교가 있는 칸에 처음으로 도착하는 시간을 출력한다. 학교에 도착할 수 있는 경로가 없다면 $-1$을 출력한다.

예제 입력 1

5
3 1 2 1 1

예제 출력 1

5

예제 입력 2

5
4 1 2 1 1

예제 출력 2

1

예제 입력 3

3
1 2 1

예제 출력 3

-1

예제 입력 4

9
1 2 2 4 2 1 1 1 1

예제 출력 4

12