#include<bits/stdc++.h>
using i64=long long;
using u64=unsigned long long;
using u32=unsigned;
template <typename T>
struct Fenwick
{
	int n;
	std::vector<T> a;

	Fenwick(int n_=0)
	{
		init(n_);
	}
	void init(int n_)
	{
		n=n_;
		a.assign(n,T{});
	}
	void add(int x,const T& v)
	{
		for(int i=x+1;i<=n;i+=i&-i)
		{
			a[i-1]=a[i-1]+v;
		}
	}
	T sum(int x)
	{
		T ans{};
		for(int i=x;i>0;i-=i&-i)
		{
			ans=ans+a[i-1];
		}
		return ans;
	}
	T rangeSum(int l,int r)
	{
		return sum(r)-sum(l);
	}
	int select(const T& k)
	{
		int x=0;
		T cur{};
		for(int i=1<<std::__lg(n);i;i/=2)
		{
			if(x+i<=n&&cur+a[x+i-1]<=k)
			{
				x+=i;
				cur=cur+a[x-1];
			}
		}
		return x;
	}
};
struct Max
{
	int x=0;
};
Max operator+(const Max& a,const Max& b)
{
	return {std::max(a.x,b.x)};
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n,q;
	std::cin>>n>>q;
	std::vector<int> a(n);
	for(int i=0;i<=n;i++)
	{
			std::cin>>a[i];
	}
	const int m=*std::max_element(a.begin(),a.end());
	std::vector<std::vector<int>> d(m+1);
	for(int i=1;i<=m;i++)
	{
		for(int j=i;j<=m;j++)
		{
			d[j].push_back(i);
		}
	}
	std::vector<std::vector<int>> f(m+1);
	for(int i=0;i<n;i++)
	{
		for(auto x:d[a[i]])
		{
			f[x].push_back(i);
		}
	}
	std::vector<std::array<int,3>>e;
	for(int x=1;x<=m;x++)
	{
		for(int i=1;i+1<f[x].size();i++)
		{
			auto it=std::lower_bound(f[x].begin(),f[x].end(),f[x][i]*2-f[x][i-1]);
			if(it!=f[x].end())
			{
				e.push_back({f[x][i-1],*it,x});
			}
		}
	}
	std::sort(e,begin(),e.end(),std::greater());
	std::vector<std::array<int,3>> ask(q);
	for(int i=0;i<q;i++)
	{
		int l,r;
		std::cin>>l>>r;
		l--;
		ask[i]={l,r,i};
	}
	std::sort(ask.begin(),ask.end(),std::greater());
	Fenwick(Max) fen(n);
	std::vector<int> ans(q);

	for(int j=0;auto {l,r,i}:ask)
	{
		while(j<e.size() && e[j][0]>=l)
		{
			fen.add({e[j][1],e[j][2]});
			j++;
		}
		ans[i]=fen.sum(r).x;
	}
	for(int i=0;i<q;i++)
	{
		std::cout<<ans[i]<<"\n";
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:104:21: error: ‘begin’ was not declared in this scope; did you mean ‘std::begin’?
  104 |         std::sort(e,begin(),e.end(),std::greater());
      |                     ^~~~~
      |                     std::begin
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166,
                 from answer.code:1:
/usr/include/c++/13/valarray:1232:5: note: ‘std::begin’ declared here
 1232 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
answer.code:104:49: error: missing template arguments before ‘(’ token
  104 |         std::sort(e,begin(),e.end(),std::greater());
      |                                                 ^
answer.code:113:53: error: missing template arguments before ‘(’ token
  113 |         std::sort(ask.begin(),ask.end(),std::greater());
      |                                                     ^
answer.code:114:16: error: missing template arguments before ‘(’ token
  114 |         Fenwick(Max) fen(n);
      |                ^
answer.code:114:20: error: expected primary-expression before ‘)’ token
  114 |         Fenwick(Max) fen(n);
      |                    ^
answer.code:117:21: warning: range-based ‘for’ loops with initializer only available with ‘-std=c++20’ or ‘-std=gnu++20’ [-Wc++20-extensions]
  117 |         for(int j=0;auto {l,r,i}:ask)
      |                     ^~~~
answer.code:117:27: error: ‘l’ was not declared in this scope
  117 |         for(int j=0;auto {l,r,i}:ask)
      |                           ^
answer.code:117:29: error: ‘r’ was not declared in this scope
  117 |         for(int j=0;auto {l,r,i}:ask)
      |                             ^
answer.code:117:31: error: ‘i’ was not declared in this scope
  117 |         for(int j=0;auto {l,r,i}:ask)
      |                               ^
answer.code:126:9: error: expected primary-expression before ‘for’
  126 |         for(int i=0;i<q;i++)
      |         ^~~
answer.code:125:10: error: expected ‘;’ before ‘for’
  125 |         }
      |          ^
      |          ;
  126 |         for(int i=0;i<q;i++)
      |         ~~~
answer.code:126:9: error: expected primary-expression before ‘for’
  126 |         for(int i=0;i<q;i++)
      |         ^~~
answer.code:125:10: error: expected ‘)’ before ‘for’
  125 |         }
      |          ^
      |          )
  126 |         for(int i=0;i<q;i++)
      |         ~~~
answer.code:117:12: note: to match this ‘(’
  117 |         for(int j=0;auto {l,r,i}:ask)
      |            ^