Background

Description

现有n个数字，现采取k次操作，每次操作可以让某一个正整数减一，另一个数加一，最终让里面的最大值和最小值的差距最大

Format

Input

第一行一个整数n(n≤1000000)

接下来一行n个正整数ai，以空格隔开(0<=ai<=100)

最后一行一个整数k(k<=100)

Output

输出经过k次操作后，最大值减最小值的答案

Samples

3
4 7 5
3

9