Maximize Minimum Range of Contiguous Subsequences

You are given a sequence \(a\) of length \(n\). You are required to select \(k\) different contiguous subsequences of the same length \(L\) (with \(1\le L\le n-k+1\)). The chosen subsequences are \(C(a, l_1, l_1+L-1), C(a, l_2, l_2+L-1), \dots, C(a, l_k, l_k+L-1)\) where \(1\le l_1<l_2<\dots< l_k\le n-L+1\).

For each contiguous subsequence, define its range as the difference between its maximum and minimum element. Let \(X\) be the minimum range among the chosen \(k\) subsequences. Your task is to maximize \(X\). In the case of ties (i.e. multiple values of \(L\) leading to the same maximum \(X\)), you should choose the smallest \(L\).

Input: A sequence \(a\) of length \(n\), an integer \(k\), and the sequence elements.

Output: Two integers: the maximized value of \(X\) and the corresponding minimum \(L\) achieving that maximum.

All formulas are represented in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(k\) separated by space.

The second line contains \(n\) integers representing the sequence \(a\).

outputFormat

Output two integers separated by a space: the maximum possible value of \(X\) and the minimum \(L\) that achieves this maximum.

sample

5 2
1 5 3 2 8

4 2