#define pii pair <int, int> #define fi first #define se second #define ll long long #define INFLL 0x3f3f3f3f3f3f3f3f #define N 3000010 int n, a[N]; ll b[N];
structCartesian_Tree { structnode { int id, val, fa; int son[2]; node() {} node (int id, int val, int fa) : id(id), val(val), fa(fa) { son[0] = son[1] = 0; } }t[N]; int root; pii b[N]; voidinit(){ t[0] = node(0, -1e9, 0); } voidbuild(int n, int *a){ for (int i = 1; i <= n; ++i) { t[i] = node(i, a[i], 0); } for (int i = 1; i <= n; ++i) { int k = i - 1; while (t[k].val > t[i].val) { k = t[k].fa; }
intmain(){ n = read(); for (int i = 1; i <= n; ++i) a[i] = read(); b[0] = 0; for (int i = 1; i <= n; ++i) { b[i] = read(); b[i] += b[i - 1]; } CT.init(); CT.build(n, a); CT.DFS(CT.root); ll res = -INFLL; seg.build(1, 0, n); for (int i = 1; i <= n; ++i) { int l = i - CT.b[i].fi, r = i + CT.b[i].se; seg.resl = seg.query(1, 0, n, l - 1, i - 1); seg.resr = seg.query(1, 0, n, i, r); res = max(res, 1ll * a[i] * (seg.resr.Max - seg.resl.Min)); res = max(res, 1ll * a[i] * (seg.resr.Min - seg.resl.Max)); } printf("%lld\n", res); return0; }