# 莫隊

* 主要想法：如果知道[a,b]的答案，那也可以$O(1)$的時間知道[a+1,b], [a-1, b], [a, b+1], [a, b-1]的答案，因此也是離線算法
* 但是如果指針不停的來回，複雜度扔是$O(n)$，因此重點是要盡量減少指針來回的次數
* 利用分塊法的想法，如果把區間每$\sqrt n$分成一塊，這樣一次查詢複雜度就是$O(\sqrt n)$
* 因此先把左界照分塊排序，左界分塊相同的照右界大小排序，離線複雜度是$O(n\sqrt q)$

:::info
跟直接對左界大小排序有什麼差別？
考慮這樣的查詢：
1, 1000000
2, 2
3, 1000000
4, 2
右指針走法會是1->1000000->2->1000000->2，複雜度很慘

但用莫對查詢順序會變：
2, 2
1, 1000000
4, 2
3, 1000000
而右指針走法會變1->2->1000000->2->1000000，顯然少來回了幾次
所以莫對只是一個折衷
:::

區間眾數
---

#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

LL l=1, r=1, ans=1, K;
LL cnt[100010]={0}, num[100010], cntcnt[100010]={0};

struct qy{
	LL l, r, id;
	bool operator<(const qy& q){
		return l/K==q.l/K?r<q.r:l/K<q.l/K;
	}
};

void add(LL a){
	cntcnt[cnt[a]]--;
	cnt[a]++;
	cntcnt[cnt[a]]++;
	ans=max(ans, cnt[a]);
}

void sub(LL a){
	cntcnt[cnt[a]]--;
	cnt[a]--;
	cntcnt[cnt[a]]++;
	if(cnt[a]+1==ans && cntcnt[cnt[a]+1]==0) ans=cnt[a];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    LL n, m;
    cin>>n>>m;
    K=sqrt(n);
    
    vector<qy> qry(m);
    rep(i,1,n+1) cin>>num[i];
    rep(i,0,m){
        cin>>qry[i].l>>qry[i].r;
        qry[i].id=i;
    }
    sort(ALL(qry));
    vector<pair<LL,LL>> res(m);
    
    cnt[num[1]]=1;
    cntcnt[1]=1;
    for(auto a:qry){
        while(l<a.l) sub(num[l++]);
        while(l>a.l) add(num[--l]);
        while(r<a.r) add(num[++r]);
        while(r>a.r) sub(num[r--]);
        res[a.id]={ans, cntcnt[ans]};
    }
	for(auto a:res) cout<<a.F<<" "<<a.S<<NL;
}