https://www.luogu.com.cn/problem/P1903

const int N = 1e6+10;
struct node
{
    int l, r, id;
}q[N];
int n, m, len, pos[N];
ll a[N], b[N], ans[N], cnt[N], c[N];
ll res, last;
bool cmp(node a, node b)
{
    if (pos[a.l] != pos[b.l]) return a.l < b.l;
    return a.r < b.r;
}
ll calc(int l, int r)
{
    ll mx = 0;
    for (int i = l; i <= r; i++) c[a[i]] = 0;
    for (int i = l; i <= r; i++)
    {
        ++c[a[i]];
        mx = max(mx, c[a[i]] * b[a[i]]);
    }
    return mx;
}
void add(int x)
{
    ++cnt[x];
    res = max(res, cnt[x] * b[x]);
}
void solve()
{
    cin >> n >> m;
    len = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
        pos[i] = (i - 1) / len + 1;
    }
    int num = pos[n];
    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + n, a[i])-b;
    for (int i = 1, l, r; i <= m; i++)
    {
        cin >> l >> r;
        q[i] = { l,r,i };
    }
    sort(q + 1, q + 1 + m, cmp);
    for (int i = 1, x = 1; i <= num; i++)
    {
        res = 0;
        last = 0;
        for (int j = 1; j <= n; j++) cnt[j] = 0;
        int  div = min(len * i, n), l = div + 1, r = div;
        for (; pos[q[x].l] == i; x++)
        {
            if (pos[q[x].l] == pos[q[x].r])
            {
                ans[q[x].id] = calc(q[x].l, q[x].r);
                continue;
            }
            while (q[x].r > r) add(a[++r]);
            last = res;
            while (q[x].l < l) add(a[--l]);
            ans[q[x].id] = res;
            while (l <= div) --cnt[a[l++]];
            res = last;
        }
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}