4463. 败给了性格恶劣的天才青梅

【题目背景】

全名为《败给了性格恶劣的天才青梅，初体验全部被夺走这件事》。

若叶又输了。

【题目描述】

若叶和小牧进行了 $n$ 场比试，第 $i$ 次比试有一个压抑值，小牧可以对这些比试做任意次如下操作：

- 选择一个正整数 $j$，满足 $1 \le j \le n$。

- 对于每一个 $i$，满足 $j \le i \le n$，可以选择使第 $i$ 次比试的压抑值增大或减小（所有比试同时增大减小，即都选增大或者都选减小） $C_{i-j+p}^{p}$。在这里，$C$ 是组合数，即 $C_{i-j+p}^{p}$ 指的是从 $i-j+p$ 个物品中选择 $p$ 个的方案数（选择的顺序不重要）。

小牧想让所有比试的压抑值较为均等。请问至少进行几次操作，可以使所有比试的压抑值都变为 $k$。

【输入格式】

第一行，包含三个整数 $n,k,p$，含义如题目描述。

第二行，包含 $n$ 个整数，表示每次比试的压抑值。

【输出格式】

一个整数，表示答案。

【样例输入】

4 1 0
2 2 2 2

【样例输出】

1

【数据规模与约定】

对于 $20\%$ 的数据，保证 $p=0$。

另有 $10\%$ 的数据，保证 $0\le k,a_i\le1$。

对于 $100\%$ 的数据，保证 $1 \le n\le 10^5$，$0 \le p\le 80$，$0 \le k,a_i \le 10^6$。

大洋里