提交记录

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define min std::min
#define max std::max
#define swap std::swap
#ifndef ONLINE_JUDGE
bool online_judge = true;
#else
bool online_judge = false;
#endif

namespace IO
{
	const int N = 1e6 + 5;
	char obuf[N], * p3 = obuf; char ibuf[N], * p1 = ibuf, * p2 = ibuf;
	inline void flush() { fwrite(obuf, p3 - obuf, 1, stdout); p3 = obuf; }
	inline void putch(char x) { (p3 - obuf < N) ? (*p3++ = x) : (flush(), *p3++ = x); }
	inline char getch() { if (online_judge) return getchar(); else return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, N, stdin), p1 == p2) ? EOF : *p1++; }
	inline bool Read(char& p) { p = getch(); while (p == ' ' || p == '\n' || p == -1) { if (p == -1) return true; p = getch(); } return false; }
	inline bool Read(char* p) { char ch = getch(); while (ch == ' ' || ch == '\n' || ch == -1) { if (ch == -1) return true; ch = getch(); } while (ch != ' ' && ch != '\n' && ch != -1) { *p++ = ch; ch = getch(); } *p++ = '\0'; return ch == -1; }
	inline bool Read(std::string str) { str = ""; char ch = getch(); while (ch == ' ' || ch == '\n' || ch == -1) { if (ch == -1) return true; ch = getch(); } while (ch != ' ' && ch != '\n' && ch != -1) { str += ch; ch = getch(); } return ch == -1; }
	inline bool Read(signed& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (Read(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool Read(short& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (Read(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool Read(long long& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (Read(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool Read(__int128_t& x) { register char ch = getch(); while (ch < '0' || ch > '9') { if (ch == -1) return true; if (ch == '-') { if (Read(x)) { x = -x; return true; } x = -x; return false; } ch = getch(); } x = 0; while (ch <= '9' && ch >= '0') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch(); } if (ch == -1) return true; return false; }
	inline bool read() { return false; }
	template < typename T, typename ... T2 > inline bool read(T& x, T2& ... oth) { if (Read(x)) return true; return read(oth...); }
	inline void Write(char* ch) { register int len = strlen(ch); for (register int i = 0; i < len; i++) putch(ch[i]); }
	inline void Write(std::string ch) { register int siz = ch.size(); for (register int i = 0; i < siz; i++) putch(ch[i]); }
	inline void Write(signed x) { if (!x) { putch('0'); return ; } register int len = 0; register signed k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void Write(short x) { if (!x) { putch('0'); return ; } register int len = 0; register short k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void Write(long long x) { if (!x) { putch('0'); return ; } register int len = 0; register long long k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void Write(__int128_t x) { if (!x) { putch('0'); return ; } register int len = 0; register __int128_t k1 = x; register char c[50] = {}; if (k1 < 0) k1 = -k1, putch('-'); while (k1) c[len++] = k1 % 10 ^ 48, k1 /= 10; while (len--) putch(c[len]); }
	inline void write() {  }
	template < typename T, typename ... T2 > inline void write(T x, T2 ... oth) { Write(x); write(oth...); }
}
using IO::read; using IO::write; using IO::flush; using IO::putch; using IO::getch;

const int N = 1e5 + 5, M = 1e6;
int n, m;
int a[N], sq, b[N], c[N], IDX;
int IIdx[M], iidx, cnt[N];
struct Query { int l, r, id; }; Query query[N];
int ans[N];
int l, r, ma;
int from[N], G, H, idx;
int L[N], R[N];
inline void add(int x)
{
	IIdx[++iidx] = c[x];
	cnt[c[x]]++;
	ma = max(ma, a[x] * cnt[c[x]]);
}
inline void solve()
{
	read(n, m);
	sq = sqrt(n);
	for (register int i = 1; i <= n; i++)
	{
		read(a[i]);
		from[i] = (i - 1) / sq + 1;
		if (from[i] != from[i - 1]) L[from[i]] = i;
		R[from[i]] = i;
		b[i] = a[i];
	}
	std::sort(b + 1, b + 1 + n);
	IDX = std::unique(b + 1, b + 1 + n) - b - 1;
	for (register int i = 1; i <= n; i++) c[i] = std::lower_bound(b + 1, b + 1 + IDX, a[i]) - b;
	for (register int i = 1; i <= m; i++)
	{
		read(l, r);
		if (from[l] == from[r])
		{
			for (register int i = 1; i <= iidx; i++) cnt[IIdx[i]] = 0;
			iidx = 0, ma = 0;
			for (register int i = l; i <= r; i++)
			{
				if (!cnt[c[i]]) IIdx[++iidx] = c[i];
				cnt[c[i]]++;
				ma = max(ma, cnt[c[i]] * a[i]);
			}
			ans[i] = ma;
		}
		else query[++idx] = { l, r, i };
	}
	ma = 0;
	for (register int i = 1; i <= iidx; i++) cnt[IIdx[iidx]] = 0;
	iidx = 0;
	std::sort(query + 1, query + 1 + idx, [](Query a, Query b) { return from[a.l] < from[b.l] || from[a.l] == from[b.l] && a.r < b.r; });
	l = 1, r = 0;
	for (register int i = 1; i <= idx; i++)
	{
		if (from[query[i].l] != from[query[i - 1].l])
		{
			l = R[from[query[i].l]] + 1, r = R[from[query[i].l]];
			while (iidx) { cnt[IIdx[iidx]]--; iidx--; }
			ma = 0;
		}
		while (r < query[i].r) add(++r);
		G = iidx, H = ma;
		while (l > query[i].l) add(--l);
		ans[query[i].id] = ma;
		l = R[from[query[i].l]] + 1;
		while (iidx > G) { cnt[IIdx[iidx]]--; iidx--; }
		ma = H;
	}
	for (register int i = 1; i <= m; i++)
	{
		write(ans[i], "\n");
	}
}
signed main()
{
	register int t = 1;
	// read(t);
	while (t--) solve();
	flush();
}