T1 WA 85pts 求调

WA on #14 #15 #18 QwQ

#include <iostream>
#include <algorithm>
#define ll __int128
using namespace std;
const int N = 2e6 + 10;
int n, a[N], sz[N], f[N]; bool in[N]; ll ans;
struct node { int x, id; bool operator < (const node &k) const { return x < k.x; } } b[N];
int rd() {
	int res = 0; bool f = 0; char ch = getchar();
	while (ch < '0' || ch > '9') f |= ch == '-', ch = getchar();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
	return f ? -res : res;
}
int get_fa(int x) { return x == f[x] ? x : f[x] = get_fa(f[x]); }
void merge(int x, int y) {
	if (! in[y]) return ;
	int fx = get_fa(x), fy = get_fa(y);
	if (fx != fy) {
		if (a[fx] > a[fy]) f[fy] = fx, sz[fx] += sz[fy];
		else f[fx] = fy, sz[fy] += sz[fx];
	}
}
void print(ll x) {
	if (x > 10) print(x / 10);
	putchar((x % 10) ^ 48);
}
signed main() {
	n = rd();
	for (int i = 1; i <= n; ++ i) a[i] = rd(), b[i] = {a[i], i}, f[i] = i, sz[i] = 1;
	sort(b + 1, b + n + 1);
	for (int i = n; i; -- i) {
		int j = b[i].id; in[j] = true;
		if (j != 1) merge(j, j - 1);
		if (j != n) merge(j, j + 1);
		ans = max(ans, (ll) sz[get_fa(j)] * a[j] * a[get_fa(j)]);
	}
	print(ans);
	return 0;
}