原题链接：Problem - D - Codeforces

题意：给你长度为n的数组，可以无限次的让i位置的数-1，让i+1的位置的数+1。问最大值-最小值的最小值是多少？

思路：可以观察出，操作的真正意义是让i位置的数减少，i后面的数增加，如果p[i+1]<p[i]那么操作一定是优秀的，从感性的角度理解，就是让数组变得平均，但是直接模拟，会导致超时。观察可以知道，最后形成的数组，一定是单调的，后面大于前面，并且有很多相同的数，因为要处理这些相同的数，所以导致超时，那么就可以用栈来优化这个过程。栈存放的元素类型是pair，第一维放值，第二维放数量。对于每一个数，初始sum=p[i]，cnt=1，如果sum/cnt<=栈顶的值，那么就可以减少栈顶的值，让当前的值增加，也就是sum+栈顶的值*数量，cnt+数量。这样也就是总和为sum，然后分到cnt个位置的问题，因为要尽可能的平均，那么就如果sum能整除cnt，那么就往栈里面放入sum/cnt和cnt，如果不能整除，那么就放入sum/cnt，cnt-sum%cnt和sum/cnt+1，sum%cnt。

为什么是这样，可以看下面的图片。

//冷静，冷静，冷静
//调不出来就重构
//#pragma GCC optimize(2)
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define endl '\n'
#define count2(x) __builtin_popcountll(x)
#define is2(x) __builtin_ffsll(x)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10,mod=1000000007;
ll p[N];
void Jiuyuan()
{ll n;cin>>n;ll mx=0;for(int i=1;i<=n;i++){cin>>p[i];}stack<pii> st;for(int i=1;i<=n;i++){ll sum=p[i],cnt=1;while(st.size()&&st.top().first>=sum/cnt){sum+=st.top().first*st.top().second;cnt+=st.top().second;st.pop();}st.push({sum/cnt,cnt-sum%cnt});if(sum%cnt){st.push({sum/cnt+1,sum%cnt});}}ll max1=0,min1=1e18;while(st.size()){max1=max(max1,st.top().first);min1=min(min1,st.top().first);st.pop();}cout<<max1-min1<<endl;
}
int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);ll T=1;cin>>T;while(T--){Jiuyuan();}return 0;
}