#include <bits/stdc++.h>
using namespace std;

int main(){

	int n, q; cin >> n >> q;
	vector<int> a;
	int  p = 4;
	vector<int> k;
	int broj;
	
	for (int i = 0; i < p; i++) {
		k.push_back(0);
	}

	for (int i = 0; i < n; i++) {
		cin >> broj;
		a.push_back(broj);
	}
	
	int l, d;
	
	for(int i = 0; i < q; i++) {
		cin >> l >> d;
		l--; d;
		for(int j = l; j < d; j++){
			if(a[j] == 1)
				k[0]++;
			if(a[j] > 1 and a[j] < 4)
				k[1]++;
			if(a[j] > 3 and a[j] < 8)
				k[2]++;
			if(a[j] > 7 and a[j] < 16)
				k[3]++;
		}
		
		int maks = 0;
		
		for(int j = 0; j < p; j++) {
			if(k[j] > maks)
				maks = k[j];
		}
		
		cout << maks << '\n';
		
		for(int j = 0; j < p; j++) 
			k[j] = 0;
	}
	
	return 0;
}