#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
const int maxn(30);
const int esp=-100000;
#define MAXN maxn
#define upf(a,b,c) for(int a=b;a<=c;++a)
#define drf(a,b,c) for(int a=b;a>=c;--a)
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
ll dp[3005],n;
ll p[3005];
ll inv[3005];
void getn(ll m){
    p[0]=1;
    p[1]=m;
    upf(i,2,m){
        p[i]=(p[i-1]*(m-i+1))%mod*inv[i];
        p[i]%=mod;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    upf(i,1,3000){
        inv[i]=powmod(i,mod-2);
    }
    dp[0]=0;
    dp[1]=0;
    upf(i,2,3000){
        getn(i);
        ll tmp=powmod(2,i);
        dp[i]=((tmp*i*(i-1))%mod*powmod(((tmp-1)*4)%mod,mod-2))%mod;
        ll ttp=powmod((tmp-1)%mod,mod-2);
        upf(j,2,i-1){
            dp[i]+=((p[j]*dp[j])%mod)*ttp;
            dp[i]%=mod;
        }
    }
    upf(i,1,3000){
        dp[i]+=dp[i-1];
        dp[i]%=mod;
    }
    upf(i,1,3000){
        dp[i]*=inv[i];
        dp[i]%=mod;
    }
    while(cin>>n){
        cout<<dp[n]<<endl;
    }

}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
const ll mod(1e6+3);
const ll INF(0x3f3f3f3f3f3f3f3f);
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
const int MAXN(1e5+7);

int N, C, K;
int bck[MAXN], numm[MAXN];
int a[MAXN];
set<int> noww;
int mxlen, lp, nlen;

ll ss[1000007];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ss[1] = 1;
    per(i, 2, mod) {
        ss[i] = i*ss[i-1]%mod;
    }
    ll n;
    while(cin >> n) {
        if(n>=mod) {
            cout << 0 << '\n';
        } else {
            cout << ss[n] << '\n';
        }
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
const ll mod(998244353);
const ll INF(0x3f3f3f3f3f3f3f3f);
#define w(i) T[(i)].w
#define ls(i) T[(i)].ls
#define rs(i) T[(i)].rs
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
const int MAXN(1e5+7);

int N, Q;
int L[MAXN], R[MAXN];

struct node{
    int ls,rs;
    ll w;
    node(){ls=rs=w=0;}
}T[MAXN*20];
ll a[MAXN],b[MAXN],p[MAXN];
int root[MAXN],sz;
int cmp(int i,int j){
    return a[i]<a[j];
}
int n,m;
void ins(int &i,int l,int r,int x){
    T[++sz]=T[i]; i=sz;
    w(i)++;
    if (l==r) return;
    int m=(l+r)>>1;
    if (x<=m) ins(ls(i),l,m,x);
    else ins(rs(i),m+1,r,x);
}
int query(int i,int j,int l,int r,int k){
    if (l==r) return l;
    int t=w(ls(j))-w(ls(i));
    int m=(l+r)>>1;
    if (t>=k) return query(ls(i),ls(j),l,m,k);
    else return query(rs(i),rs(j),m+1,r,k-t);
}

inline ll solve(int& pos) {
    ll Ans=-1;
    ll lenn, lenn1, lenn3, summ;
    int rg=R[pos]-L[pos]+2;
    lenn=a[p[query(root[L[pos]-1], root[R[pos]], 1, N, rg-1)]];
    lenn1=a[p[query(root[L[pos]-1], root[R[pos]], 1, N, rg-2)]];
    summ = lenn+lenn1;
    per(i, 3, rg) {
        lenn3=a[p[query(root[L[pos]-1], root[R[pos]], 1, N, rg-i)]];
        summ+=lenn3;
        if(lenn3+lenn1>lenn) {
            Ans=summ;
            break;
        }
        summ-=lenn;
        lenn = lenn1;
        lenn1 = lenn3;
    }
    return Ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while(cin >> N >> Q) {
        n=N;m=Q;
        root[0]=0;
        per(i, 1, N+1) {
            cin >> a[i];p[i]=i;
        }
        sort(p+1, p+1+N, cmp);
        per(i, 1, N+1) {b[p[i]] = i;}
        sz=0;
        per(i, 1, N+1) {
            root[i]=root[i-1];
            ins(root[i], 1, N, b[i]);
        }
        per(i, 1, Q+1) {
            cin >> L[i] >> R[i];
            cout << solve(i) << '\n';
        }

    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define per(i,a,n) for (int i=a;i<n;i++)
#define rep(i,a,n) for (int i=n-1;i>=a;i--)
const ll mod(998244353);
const ll INF(0x3f3f3f3f3f3f3f3f);
ll powmod(ll a, ll b) { ll res = 1; a %= mod; assert(b >= 0); for (; b; b >>= 1) { if (b & 1)res = res * a%mod; a = a * a%mod; }return res; }
const int MAXN(1e5+7);

int N, C, K;
int bck[MAXN], numm[MAXN];
int a[MAXN];
int mxlen, lp, nlen;
set<int> wtt;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while(cin >> N >> C >> K) {
        wtt.clear();
        mxlen=nlen=0;
        per(i, 1, C+1) {numm[i]=bck[i]=0;}
        per(i, 1, N+1) {cin >> a[i];bck[a[i]]++;}
        lp = 1;
        per(i, 1, N+1) {
            if(numm[a[i]]<K) {
                if(bck[a[i]]+numm[a[i]]>=K) {
                    if(!numm[a[i]]) wtt.insert(a[i]);
                    numm[a[i]]++;
                    nlen++;
                    if(numm[a[i]]==K) wtt.erase(a[i]);
                } else {
                    int flag1=1;
                    per(j, lp, i) {
                        if(flag1 && wtt.empty()) {
                            mxlen=max(mxlen, nlen);
                            flag1=0;
                        }
                        --numm[a[j]];
                        --nlen;
                        if(!numm[a[j]]) wtt.erase(a[j]);
                        else if(numm[a[j]]<K) wtt.insert(a[j]);
                    }
                    nlen = 0;
                    lp = i+1;
                }
            } else {
                numm[a[i]]++;
                nlen++;
            }
            bck[a[i]]--;
        }
        //结束判断
        per(j, lp, N+1) {
            if(wtt.empty()) {
                mxlen=max(mxlen, nlen);
                break;
            }
            --numm[a[j]];
            if(!numm[a[j]]) wtt.erase(a[j]);
            else if(numm[a[j]]<K) wtt.insert(a[j]);
        }
        cout << mxlen << endl;
    }

    return 0;
}