Suppose we have $$n$$ cities with integer coordinate on a line. First, we have to select a city to be the capital. Then in each operation, we have to choose a non-capital city and change it's coordinate by $$1$$ ($$-1$$ or $$+1$$). We have to pick the capital and do the operations exactly $$k$$ time so that the sum of distances from cities to the capital is minimized. Print the index of the selected capital and the desired sum after exactly $$k$$ operations. If there are multiple such choices, output the smallest index of an optimal capital.
You are required to print the index of the selected capital and required sum after \(k\) operations. If there are multiple such choices, print the smallest index of an optimal capital.
Input format
- First line: Two integers \(n\) and \(k\) \(1 \le n \le 300\ 000\)
- Second line: \(n\) integers where the \(i^{th}\) integer that contains the coordinate of the \(i^{th}\) city
Output format
Print two integers that represent the index of the capital and the minimized required sum respectively.
Constraints
\(1 \le n \le 300\ 000\)
\(0 \le k, A_i \le 10^9\)
Sample input #2
5 47019 19912129 5 7138912 913 200134
Sample output #2
5 27003104