시소 timer 2s memory 1024MB

길이 10^9의 막대기가 수평으로 놓여 있다. 막대기 자체의 무게는 무시한다. 서로 같은 양수의 무게를 가진 단위 추 N개가 막대기 위에 놓여 있다. 단위 추 N개의 위치는 모두 다르다. i번째 단위 추는 막대기의 왼쪽 끝에서 Ai 떨어진 위치에 놓여 있다.

너비 w의 상자가 있다면, 막대기를 상자 위에 적당히 올려놓아서, 막대기의 왼쪽 끝에서 l미터 떨어진 지점부터 왼쪽 끝에서 r미터 떨어진 지점까지가 상자와 맞닿게끔 할 수 있다. 이때, 0 <= l < r <= 10^9, r = l + w를 만족해야 한다. l과 r을 한 번 정하면 수정할 수 없다.

상자를 올려놓은 다음에는, 현재 올라가 있는 단위 추 중 가장 왼쪽에 있는 것 혹은 가장 오른쪽에 있는 것 중 하나를 적절하게 선택하여 제거한다. 이 시행을 총 N-1회 반복하면 결국 추가 하나만 남을 것이다. 이 과정에서, 처음 상태와 최종 상태를 포함해서 항상 무게중심의 위치는 막대기의 왼쪽 끝에서 l미터 이상 r미터 이하 떨어져 있어야 한다. 다시 말해서, b1, b2, ..., bm의 위치에 단위 추가 놓여 있는 순간에는, l <= (b1 + b2 + ... + bm) / m <= r이어야 한다.

당신의 목표는 이것이 가능하게 하는 상자의 너비 w의 최솟값을 구하는 것이다.