#include <bits/stdc++.h>
using namespace std;
int p[1000005];
 
int getSum(int* BIT,int idx){
	int sum=0;
	while(idx>0){
		sum+=BIT[idx];
		idx-=(idx&-idx);
	}
	return sum;
}
 
void update(int* BIT,int N,int idx,int val){
	while(idx<=N){
		BIT[idx]+=val;
		idx+=(idx&-idx);
	}
	return;
}
 
int main() {
	memset(p,0,sizeof(p));
	
	int N,i;
	scanf("%d",&N);
	int Q;
	scanf("%d",&Q);

	int A[N+1];
	for(i=1;i<=N;i++)
	scanf("%d",&A[i]);
	
	int *BIT=new int[N+1];
	for(i=0;i<=N;i++)
	BIT[i]=0;
	
	
	vector<pair<int,pair<int,int> > > queries(Q);
	for(i=0;i<Q;i++){
		scanf("%d %d",&queries[i].second.first,&queries[i].first);
		queries[i].second.second=i;
	}
	vector<int> ans(Q,0);
	sort(queries.begin(),queries.end());
	int j=0;
	for(i=1;i<=N;i++){
		if(p[A[i]]>0)
		update(BIT,N,p[A[i]],-1);
		p[A[i]]=i;
		update(BIT,N,i,1);
		while(j<Q&&queries[j].first==i){
			ans[queries[j].second.second]=getSum(BIT,i)-getSum(BIT,queries[j].second.first-1);
			++j;
		}
		if(j==Q)
		break;
	}
	
	for(int i=0;i<Q;i++)
	printf("%d\n",ans[i]);
	// your code goes here
	return 0;
} 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
	while(1){
		llong n, m;
		scanf("%lld%lld", &n, &m);
		if(n==0) return 0;

		vector<llong> v(n);
		REP(i, n){
			scanf("%lld", &v[i]);
		}
		v.push_back(0);
		n++;

		vector<llong> a;
		REP(i, n){
			REP(j, n){
				a.push_back(v[i]+v[j]);
			}
		}
		VSORT(a);

		llong ans=0;
		REP(i, n){
			REP(j, n){
				llong tmp=v[i]+v[j];
				llong k=upper_bound(a.begin(), a.end(), m-tmp)-a.begin();
				if(k==a.size()) continue;
				k--;

				if(k>=0) ans=max(ans, tmp+a[k]);
			}
		}

		printf("%lld\n", ans);
	}
}