balalala

刚开始做这个题目以为是贪心？？？唉，一直没思路，后来看了题解，原来是二分。。。。
我们假设第x天为当前最优解,小于x的都不是最优解，如果小于x的话那么就会与当前得到的最优解矛盾，如果冲突的话我们应该更新当前最小值，大于x的都不是最优解，符合二分的条件------具有某种神秘性质（单调性）。长到第x天的话，其实只有前x % n 的水稻才会长高，其他都是增长的高度是一样的。我们让每个水稻高度相等的话肯定是向中间值靠拢才是最优的。

#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#include <ctime>
#include <list>
#include <cmath>
#include <map>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 +10;
const int mod = 1e9 + 7;
int a[N], b[N],n;
bool check(ll x)
{
    ll k = x % n;
    for (int i = 0; i < n; i++)
    {
        if (i < k)b[i] = a[i] + 1;
        else b[i] = a[i];
    }
    sort(b, b + n);
    int mid = b[n / 2];
    ll cnt = 0;
    for (int i = 0; i < n; i++) {
        cnt += abs(b[i] - mid);
    }
    return cnt <= x;
}
void solve()
{
    scanf("%d", &n); for (int i = 0; i < n; i++)scanf("%d", &a[i]);
    ll l = 1, r = 1e18;
    while (l < r)
    {
        ll mid = (l + r) >> 1;
       // cout << l<<" "<< r<< " " << mid << endl;
        if (check(mid))r = mid;
        else l = mid  + 1;
    }
    cout << l << endl;
}
int main()
{
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
#endif
    solve();
    return 0;
}