#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
using namespace std;
const int maxn = 100005,maxm = 10000005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int rt[maxn],sum[maxm],ls[maxm],rs[maxm],pos,siz,n,Q;
LL a[maxn],b[maxn],tot;
void add(int& u,int v,int l,int r){
	u = ++siz; ls[u] = ls[v]; rs[u] = rs[v]; sum[u] = sum[v];
	if (l == r){sum[u]++;return;}
	int mid = (l + r) >> 1;
	if (mid >= pos) add(ls[u],ls[v],l,mid);
	else add(rs[u],rs[v],mid + 1,r);
	sum[u] = sum[ls[u]] + sum[rs[u]];
}
LL ans,L,R;
int kth(int u,int v,int l,int r,int k){
	if (l == r) return l;
	int mid = (l + r) >> 1;
	if (sum[rs[u]] - sum[rs[v]] >= k) return kth(rs[u],rs[v],mid + 1,r,k);
	return kth(ls[u],ls[v],l,mid,k - sum[rs[u]] + sum[rs[v]]);
}
void work(){
	while (Q--){
		L = read() - 1; R = read(); ans = -1;
		LL K = 1,t,tt,ttt;
		while (K + 2 <= R - L){
			t = b[kth(rt[R],rt[L],1,tot,K)];
			tt = b[kth(rt[R],rt[L],1,tot,K + 1)];
			ttt = b[kth(rt[R],rt[L],1,tot,K + 2)];
			if (t < tt + ttt) {ans = t + tt + ttt; break;}
			K++;
		}
		printf("%lld\n",ans);
	}
}
int main(){
	while (scanf("%d%d",&n,&Q)==2){
		siz = 0;
		REP(i,n) b[i] = a[i] = read();
		sort(b + 1,b + 1 + n); tot = 1;
		for (int i = 2; i <= n; i++) if (b[i] != b[tot]) b[++tot] = b[i];
		REP(i,n) a[i] = lower_bound(b + 1,b + 1 + tot,a[i]) - b;
		REP(i,n) pos = a[i],add(rt[i],rt[i - 1],1,tot);
		work();
	}
	return 0;
}

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
#define LL long long int
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define cls(s,v) memset(s,v,sizeof(s))
#define mp(a,b) make_pair<int,int>(a,b)
#define cp pair<int,int>
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 0x3f3f3f3f;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = 0; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 1) + (out << 3) + c - 48; c = getchar();}
	return flag ? out : -out;
}
int n,C,K,ans,A[maxn];
vector<int> pos[maxn];
int sc[maxn],top;
int mx[4 * maxn],L,R;
void modify(int u,int l,int r,int v){
	if (l == r){mx[u] = v; return;}
	int mid = (l + r) >> 1;
	if (mid >= L) modify(ls,l,mid,v);
	else modify(rs,mid + 1,r,v);
	mx[u] = max(mx[ls],mx[rs]);
}
int query(int u,int l,int r){
	if (l >= L && r <= R) return mx[u];
	int mid = (l + r) >> 1;
	if (mid >= R) return query(ls,l,mid);
	else if (mid < L) return query(rs,mid + 1,r);
	return max(query(ls,l,mid),query(rs,mid + 1,r));
}
void build(int u,int l,int r){
	if (l == r){mx[u] = 0; return;}
	int mid = (l + r) >> 1;
	build(ls,l,mid);
	build(rs,mid + 1,r);
	mx[u] = 0;
}
void work(){
	build(1,1,n); ans = 0; top = 0;
	for (int i = n; i; i--){
		int u = A[i];
		pos[u].push_back(i);
		sc[++top] = u;
		while (pos[sc[top]].size() >= K) top--;
		if (pos[u].size() >= K) {
			if (pos[u].size() > K){
				L = pos[u][pos[u].size() - 2];
				modify(1,1,n,0);
			}
			L = i;
			modify(1,1,n,pos[u][pos[u].size() - K]);
		}
		L = i; R = top ? pos[sc[top]][pos[sc[top]].size() - 1] - 1 : n;
		if (L <= R){
			if (query(1,1,n) <= R) ans = max(ans,R - L + 1);
		}
	}
	REP(i,C) pos[i].clear();
	printf("%d\n",ans);
}
int main(){
	while (~scanf("%d%d%d",&n,&C,&K)){
		REP(i,n) A[i] = read();
		work();
	}
	return 0;
}