Rt，题目是AT_joisc2014_c 歴史の研究,WA了一堆点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
struct qus{
	int l,r,id;
}b[N];
int n,q,a[N],len;
bool cmp(qus x,qus y){
	if(x.l / len == y.l / len) return x.r < y.r;
	else return x.l < y.l;
}
ll ans,out[N];
int t[N],o[N];
void add(int x){
	++t[x];
	ans = max(ans,(ll)t[x] * o[x]);
}
int main(){
	scanf("%d%d",&n,&q);
	len = sqrt(n);
	for(int i = 1;i <= n;++i) scanf("%d",&a[i]),o[i] = a[i];
	sort(o + 1,o + n + 1);
	for(int i = 1;i <= n;++i) a[i] = lower_bound(o + 1,o + n + 1,a[i]) - o;
	for(int i = 1;i <= q;++i){
		scanf("%d%d",&b[i].l,&b[i].r);
		b[i].id = i;
	}
	sort(b + 1,b + q + 1,cmp);
	int j = 1;
	stack<int>s;
	for(int i = 0;i <= n / len;++i){
		int l = (i + 1) * len;
		int r = l - 1;
		memset(t,0,sizeof(t));
		ans = 0;
		while(j <= q && b[j].l / len == i){
			//printf("%d %d %d\n",j,l,r);
			if(b[j].r / len == i){
				for(int k = b[j].l;k <= b[j].r;++k) add(a[k]);
				out[b[j].id] = ans;
				ans = 0;
				for(int k = b[j].l;k <= b[j].r;++k) --t[a[k]];
			} else {
				while(r < b[j].r) ++r,add(a[r]);
				int lst = ans;
				while(l > b[j].l) --l,add(a[l]),s.push(a[l]);
				out[b[j].id] = ans;
				ans = lst;
				while(!s.empty()) --t[s.top()],s.pop();
				l = (i + 1) * len;
			}
		//	printf("%d %d %d\n",j,l,r);
			++j;
		}
	}
	for(int i = 1;i <= q;++i) printf("%lld\n",out[i]);
	return 0;
}