Closer
86% Success889 Attempts30 Points1s Time Limit256MB Memory1024 KB Max Code
You are given an array \(A\) of \(N\) integers. You can perform following operations :
- Choose two distinct indices \(i\) and \(j\), increment \(A_i\) by \(1\) and decrement \(A_j\) by \(1\)
Find the minimum number of operations you should perform such that absolute difference between any two elements is at most \(K\)
Input Format:
The First line contains two integers \(N\) and \(K\) .
The second line contains the \(N\) elements of array \(A\) .
Output Format
Print the minimum number of operations.
Constraints
\(1 \leq N \leq 10^5\)
\(1 \leq K \leq 10^9\)
\(1 \leq A_i \leq 10^5\)
Examples
Input
4 3 1 5 1 10
Output
4
Explanation
In first operation we choose i=1 and j=4 so A = [2,5,1,9]
In second operation we choose i=3 and j=4 so A = [2,5,2,8]
In third operation we choose i=1 and j=4 so A = [3,5,2,7]
In fourth operation we choose i=3 and j=4 so A = [3,5,3,6]
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Loading Editor...
Results