Some days ago, I learned the concept of LCM (least common multiple). I've played with it for several times and I want to make a big number with it.

But I also don't want to use many numbers, so I'll choose three positive integers (they don't have to be distinct) which are not greater than *n*. Can you help me to find the maximum possible least common multiple of these three integers?
The first line contains an integer *n* (1 ≤ *n* ≤ 10<sup class="upper-index">6</sup>) — the *n* mentioned in the statement.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#include <cstdlib> 
#include <math.h>
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef pair< int,int > ii;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(int i=0;i<n;i++)
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c)).begin() i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define N 200005
int v[N];
vector<vector<int>> a(N,vector<int>(N,0));

int build(int x,int y)
{
if(a[x][y]) return a[x][y];
if(x==y) {a[x][x]=v[x]; return v[x];}
int mid=(y-x+1)/2;
a[x][y]=min(build(x,x+mid-1),build(x+mid,y));

}


int main()
{
	int n,q;
	cin>>n>>q;
	fo(i,n) cin>>v[i];
	int z=log(n)/log(2);
	z=pow(2,z);
	if(z==n) build(0,z-1);
	else{
		build(0,z-1);
	build(n-z,n-1);
	}
	
	int ans=0;
	int ini,fin;
	fo(i,q)
	{
     cin>>ini>>fin;
     z=log(fin-ini)/log(2);
     z=pow(2,z);
     ans=min(build(ini,ini+z-1),build(fin-z+1,fin));
     cout<<ans<<endl;
	}



}