题目描述

我们都知道罗宾汉令人印象深刻的故事。罗宾汉利用他的射箭技巧和他的智慧从富人那里偷钱，然后把它归还给穷人。

在 Kekoland 有 $n$ 个公民，每个人都有 $c_i$ 的钱币。每天，罗宾汉将从城里最富有的人身上拿出 $1$ 枚硬币，他会把它交给最贫穷的人。如果选择不是唯一的，他将随机选择其中一个。可悲的是，罗宾汉已经老了，想要在第 $k$ 天退休。他决定在最后几天帮助穷人。

罗宾汉拿走他的钱后，最富有的人也可能成为最穷的人，甚至可能会发生罗宾汉将他的钱还给他的钱。例如，如果所有人拥有相同数量的硬币，那么第二天他们也将拥有相同数量的硬币。

输出第 $k$ 天最富有的人和最穷的人硬币数量之间的差值。（第 $k$ 天罗宾汉也交换了钱）

输入格式

第一行两个整数 $n,k$，$n\le 500000$，$0\le k\le 10^9$。

第二行 $n$ 个整数 $c_i$，$1\le c_i\le 10^9$。

输出格式

输出一个整数表示答案。

4 1
1 1 4 2

2

3 1
2 2 2

0