고드름

Andrew가 가장 아끼는 Krakozyabra가 최근 달아났고, 이제 그는 Krakozyabra를 되찾고 싶어 한다!

현재 이 도망자는 얼음 동굴 안에 있다. 동굴 천장에는 정수 좌표 1부터 n까지 번호가 매겨진 위치에 고드름 n개가 매달려 있다. 바닥과 i-th 고드름 사이의 거리는 ai와 같다.

Andrew는 1부터 n까지의 범위에서 임의의 정수 지점 T를 선택하고, 시각 0에 양쪽(왼쪽과 오른쪽)으로 초당 한 지점의 속도로 퍼지는 음파를 발생시킬 수 있다. 음파에 닿은 모든 고드름은 같은 속도로 떨어지기 시작한다(즉, 일 초가 지나면 바닥과 고드름 사이의 거리가 하나 줄어들지만 영보다 작아질 수는 없다). 고드름과 바닥 사이의 거리가 영보다 큰 동안에는 그곳을 통과할 수 있는 것으로 간주하며, 그 거리가 영이 되는 즉시 고드름이 길을 막아 통과를 금지한다.

Krakozyabra는 처음에(즉, 시각 0에) 지점 에 있으며, 초당 한 지점의 속도로 오른쪽 방향으로 달리기 시작한다. 한 초 동안의 사건은 다음 순서로 일어난다고 가정할 수 있다. 먼저 Krakozyabra가 위치를 바꾸고, 그 후에야 음파가 퍼지고 고드름이 떨어진다. 특히 이는 Krakozyabra가 현재 지점 에 있고, 지점 i에서 떨어지고 있는(즉, 이미 음파에 닿은) 고드름이 바닥에서 1만큼 떨어져 있다면, Krakozyabra가 그곳을 통과하여 에 도달하고, 그 후에야 고드름이 완전히 떨어져 길을 막는다는 뜻이다.

Krakozyabra의 현재 위치에서 왼쪽과 오른쪽 양쪽 모두에 떨어진 고드름이 (i.e. with ai = 0)개 있으면 Krakozyabra가 갇힌 것으로 간주한다. T의 최적값을 선택하여 Krakozyabra를 가두는 데 걸리는 최소 시간을 Help Andrew 구하고, 이 임무가 불가능하다면 불가능하다고 알려라.

첫 줄에 고드름의 수 n (2 ≤ n ≤ 105)가 주어진다.

다음 줄에 바닥과 고드름 사이의 거리인, 공백으로 구분된 수 n개 ai (1 ≤ ai ≤ 105)가 주어진다.

Krakozyabra를 떨어진 두 고드름 사이에 가두는 데 걸리는 최소 시간을 나타내는 정수 하나만 출력한다. 불가능하다면 - 1을 출력한다.

첫 번째 예제에서는 지점 3에서 음파를 발생시키는 것이 최적이다. 그러면 이 초 뒤에 고드름 1과 5가 떨어지기 시작하고, 일 초가 더 지나면 길을 막는다. 그때 Krakozyabra는 에 있게 된다. 고드름 번호 3도 떨어져 있으므로, 실제로는 왼쪽으로 가는 길을 막는 고드름이 두 개라는 점에 유의하라.

두 번째 예제에서는 지점 2에서 음파를 발생시켜 2초 안에 Krakozyabra를 가두는 것이 최적이다.

네 번째 예제에서는 가두는 것이 불가능하다.