代码打印

#include<iostream>
#include<vector>
#include<map>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstring>
#include<stack>
#include<algorithm>
#define ll long long
using namespace std;
const int N = 1e5 + 5;

long long cnt[N], sum[N], mx[N], mn[N], pre[N], lst[N], bg[N], sm[N], n;
long long a[N], b[N];
long long ask1(int i)
{
	long long res = 0;
	while (i > 0)
	{
		res += cnt[i];
		i -= i & (-i);
	}
	return res;
}
void update1(int i)
{
	while (i <= n)
	{
		cnt[i] += 1;
		i += i & (-i);
	}
	return;
}
long long ask2(int i)
{
	long long res = 0;
	while (i > 0)
	{
		res += sum[i];
		i -= i & (-i);
	}
	return res;
}
void update2(int i, int k)
{
	while (i <= n)
	{
		sum[i] += k;
		i += i & (-i);
	}
	return;
}
int main() {
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 1; i <= n; ++i)
			cin >> a[i], b[i] = a[i];
		map<long long, int> mp;
		sort(b + 1, b + 1 + n);
		b[0] = -1e10;
		int idx = 0;
		for(int i = 1; i <= n; ++i)
			if (b[i] != b[i - 1])
			{
				if (mp.find(b[i]) == mp.end())
					mp[b[i]] = ++idx;
			}
		memset(cnt, 0, sizeof(cnt));
		memset(sum, 0, sizeof(sum));
		memset(mx, 0, sizeof(mx));
		memset(mn, 0x3f, sizeof(mn));
		memset(bg, 0, sizeof(mx));
		memset(sm, 0x3f, sizeof(mn));
		memset(lst, 0, sizeof(mx));
		memset(pre, 0x3f, sizeof(mn));
		for (int i = 1; i <= n; ++i)
		{
			mn[i] = min(mn[i - 1], a[i]);
			update1(mp[a[i]]);
			update2(mp[a[i]], a[i]);
			bg[i] = ask2(n) - ask2(mp[a[i]]);
			pre[i] = ask1(n) - ask1(mp[a[i]]);
		}
		memset(cnt, 0, sizeof(cnt));
		memset(sum, 0, sizeof(sum));
		for (int i = n; i >= 1; --i)
		{
			mx[i] = max(mx[i + 1], a[i]);
			update1(mp[a[i]]);
			update2(mp[a[i]], a[i]);
			sm[i] = ask2(mp[a[i]] - 1);
			lst[i] = ask1(mp[a[i]] - 1);
		}
		long long ans = 1e18;
		for (int i = 1; i <= n; ++i)
		{
			ans = min(ans, mx[i] - mn[i] + lst[i] * a[i] - sm[i] + bg[i] - pre[i] * a[i]);
		}
		cout << ans << "\n";
	}
	return 0;
}