题意：

给一个序列 $a_n$ 问 $q$ 组询问区间 $x \times \operatorname{cnt}(l, r, x)$ 最大值。

$1 \leq n, q \leq 10 ^ 5, 1 \leq a_i \leq 10^9$ 。

题解：

用普通莫队，转化成维护单点插入，求 $\max$ 。

注意到这个数值非常大，不能直接值域分块。

但是由于 $\sum_{x} x \times cnt_x = n$ ，所以值域本质大小是 $n$ 。离散化之后对离散化的结果进行值域分块即可，$\mathcal{O}(1)$ 插入删除， $\mathcal{O}(\sqrt n)$ 查询。

预处理 $f(x, y)$ 表示 $x \times y$ 在值域中的排名 $(1 \leq y \leq cnt_x)$ 。这部分复杂度是 $\mathcal{O}(n \log n)$ 的。

复杂度 $\mathcal{O}(n \sqrt m + m \sqrt n + (n + m) \log n)$ 。

struct block {
#define gb(x) (((x)-1)/bs)
#define hob(x) ((x)*bs+1)
#define eob(x) min(((x)+1)*bs,n)
    vector<int> cnt, tag;
    int n, bs, nb;
    void init(int _n) {
        n = _n;
        bs = sqrt(n);
        nb = n / bs + 1;
        cnt.resize(n + 1);
        tag.resize(nb);
    }
    void insert(int x) {
        ++ cnt[x]; ++ tag[gb(x)];
    }
    void erase(int x) {
        -- cnt[x]; -- tag[gb(x)];
    }
    int qry() {
        int b = gb(n);
        while(~b && tag[b] == 0) -- b;
        if(b == -1) return -1;
        per(i,eob(b),hob(b)) if(cnt[i]) return i;
        return -1;
    }
} blk;

vector<int> belong;
struct ask { int l, r, id; };
inline bool mocmp(ask &a, ask &b) { return belong[a.l] ^ belong[b.l] ? belong[a.l] < belong[b.l] : belong[a.l] & 1 ? a.r < b.r : a.r > b.r; }

vector<int> cnt, a, b;
vector<ll> xcnt;
vector<ll>::iterator edx;
vector< vector<int> > f;
inline void prework(int n) {
    cnt.resize(n);
    xcnt.resize(n);
    f.resize(n + 1);
    b.resize(n);
    int p = -1;
    rep(i,0,n - 1) b[i] = a[i + 1];
    sort(b.begin(), b.end());
    auto edb = unique(b.begin(), b.end());
    rep(i,1,n) a[i] = lower_bound(b.begin(), edb, a[i]) - b.begin();
    rep(i,1,n) {
        ++ cnt[a[i]];
        xcnt[++ p] = 1ll * cnt[a[i]] * b[a[i]];
    }
    sort(xcnt.begin(), xcnt.end());
    edx = unique(xcnt.begin(), xcnt.end());
    rep(i,0,n - 1) if(cnt[i]) {
        f[i].resize(cnt[i] + 1);
        rep(j,1,cnt[i])
            f[i][j] = lower_bound(xcnt.begin(), edx, 1ll * j * b[i]) - xcnt.begin() + 1;
    }
    cnt.assign(n, 0);
}

inline void add(int x) {
    if(cnt[a[x]]) blk.erase(f[a[x]][cnt[a[x]]]);
    ++ cnt[a[x]];
    blk.insert(f[a[x]][cnt[a[x]]]);
}

inline void del(int x) {
    blk.erase(f[a[x]][cnt[a[x]]]);
    if(-- cnt[a[x]] != 0) blk.insert(f[a[x]][cnt[a[x]]]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    belong.resize(n + 1);
    a.resize(n + 1);
    int mbs = max(1.0, n / sqrt(m * 2.0 / 3));
    rep(i,1,n) belong[i] = i / mbs + 1;
    vector<ask> as(m);
    vector<ll> ans(m);
    rep(i,1,n) cin >> a[i];
    repp(i,0,m) cin >> as[i].l >> as[i].r, as[i].id = i;
    sort(as.begin(), as.end(), mocmp);
    int l = 1, r = 0;
    prework(n);

    blk.init(n);
    for(ask &cur : as) {
        // expand first
        while(r < cur.r) add(++ r);
        while(l > cur.l) add(-- l);
        while(r > cur.r) del(r --);
        while(l < cur.l) del(l ++);
        ans[cur.id] = xcnt[blk.qry() - 1];
    }
    repp(i,0,m) cout << ans[i] << '\n';
    return 0;
}