Square-Root Decomposition(MIN).txt

#include<bits/stdc++.h>
using namespace std;
 
int INF = 1e9+7;
 
int main()
{
	int n;
	cin >> n;
	vector<int> array(n);
	for(int i=0;i<n;i++)
	{
		cin >> array[i];
	}
	
	int len = (int)sqrtl(n) + 1;
	vector<int> b(len, INF);
	
	for(int i=0;i<n;i++)
	{
		b[i/len] = min(b[i/len], array[i]);
	}
	
	int q;
	cin >> q;
	
	while(q--)
	{
		int l,r;
		cin >> l >> r;
		int ans = INF;
		for(int i=l;i<=r;)
		{
			if(i%len == 0 && i+len-1 <= r)
			{
				ans = min(ans, b[i/len]);
				i += len;
			}
			else
			{
				ans = min(ans, array[i]);
				i++;
			}
		}
		cout << ans << "\n";
	}
	
	return 0;
}