Informática Avançado Semana 59

Igualdade

É dado uma lista A de N (1 \leq N \leq 10^5) inteiros. Você pode realizar a seguinte operação na lista:

    • Escolher dois índices distintos i e j, aumentar o valor de A_i em 1 em diminuir o valor de A_j em 1.

Encontre o menor número de operações para que a diferença absoluta entre quaisquer dois elementos seja no máximo K (1 \leq K \leq 10^9)

Os valores de A variam entre 1 e 10^5.

Entrada

A primeira linha contém dois inteiros N e K.

A segunda linha contém os N elementos da lista A.

Saída

Você deve imprimir o números mínimo de operações que devem ser realizadas.

Exemplos

Entrada Saída Explicação
4 3
1 5 1 10
4 1 5 1 10
2 5 1 9
3 5 1 8
3 5 2 7
3 5 3 6
3 1
1 2 3
1 1 2 3
2 2 2
6 2
1 1 7 2 3 4
3 1 1 7 2 3 4
2 1 6 2 3 4
2 2 5 2 3 4
2 2 4 2 4 4