记录编号	601363	评测结果	AAAAAAAAAA
题目名称	1975.奶牛排序	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	0.156 s
提交时间	2025-06-16 21:09:29	内存使用	2.46 MiB

#include <cstdio>
#include <cstring>
typedef long long ll;
#define isdigit(ch) ((ch) >= '0' && (ch) <= '9')
#define lowbit(x) (x & -x)
#define max(__a, __b) [&](int _a, int _b) {return _a > _b ? _a : _b;} ((__a), (__b))

template <typename T> T read() {
	T res = 0, f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
	return res * f;
}

template <typename T> void write(T x, char ed = '\n') {
	if (x < 0) putchar('-'), x = -x;
	static int sta[16], top = 0;
	do {
		sta[++top] = x % 10;
		x /= 10;
	} while(x);
	while (top) {
		putchar(sta[top--] ^ 48);
	}
	putchar(ed);
}

const int MAXN = 1e5 + 10;

int n;
int maxx = -1;
ll ans;
int a[MAXN], l[MAXN], r[MAXN];
int tree[MAXN];

void add(int x, int y) {
	for (; x <= maxx; x += lowbit(x)) tree[x] += y;
} 

int ask(int x) {
	int res = 0;
	for (; x; x -= lowbit(x)) res += tree[x];
	return res;
}

int main() {
	freopen("cow.in", "r", stdin);
	freopen("cow.out", "w", stdout);
	n = read<int>();
	for (int i = 1; i <= n; ++i) {
		a[i] = read<int>();
		maxx = max(maxx, a[i]);
	}
	for (int i = 1; i <= n; ++i) {
		l[i] = ask(maxx) - ask(a[i]);
		add(a[i], 1);
	}
	memset(tree, 0, sizeof tree);
	for (int i = n; i >= 1; --i) {
		r[i] = ask(a[i] - 1);
		add(a[i], 1);
	}
	for (int i = 1; i <= n; ++i) {
		ans += (ll)(l[i] + r[i]) * a[i];
	}
	write(ans);
	return 0;
}