같은 길이 부분 배열 합 차이

배열 A가 주어진다. s(i, k)를 A의 i번째 원소부터 시작하는 연속한 k개 원소의 합으로 정의한다.

s(i, k) = A[i] + A[i+1] + ... + A[i+k-1]

두 구간 [i, i+k-1]와 [j, j+k-1]가 겹치지 않으려면 i+k <= j이다. 가능한 모든 양의 정수 k에 대해, 겹치지 않는 같은 길이의 두 연속 부분 배열을 골라 두 합의 절댓값 차이 |s(i, k) - s(j, k)|를 최소로 하라.

첫째 줄에 자연수 n이 주어진다. n은 2 이상 3,000 이하이다.

둘째 줄에는 배열 A의 원소가 A[0]부터 A[n-1]까지 차례대로 주어진다. 각 A[i]는 0 이상 1,000,000,000 이하의 정수이다.

첫째 줄에 전체 최소 차이를 만드는 k를 출력한다.

둘째 줄에 그 최소 차이를 출력한다. 같은 최소 차이를 만드는 k가 여러 개라면 가장 큰 k를 출력한다.