struct Sparse_table
{
	vector < int > f;
	vector < vector < int > > t, pr;
	int sz, n;

	Sparse_table() {}
	Sparse_table(vector < int > & a, vector < int > & b)
	{
		n = (int)a.size();
		sz = log2(n) + 1;
		f.resize(n + 1);
		pr = vector < vector < int > > (sz, vector < int > (n));
		t = vector < vector < int > > (sz, vector < int > (n));
		f[1] = 0;
		for (int i = 2; i <= n; i++)
			f[i] = f[i / 2] + 1;
		for (int i = 0; i < n; i++)
		{
			t[0][i] = a[i];
			pr[0][i] = b[i];
		}
		for (int j = 1; j < sz; j++)
		{
			for (int i = 0; i + (1 << j) < n; i++)
			{
				if (t[j - 1][i] < t[j - 1][i + (1 << (j - 1))])
				{
					t[j][i] = t[j - 1][i];
					pr[j][i] = pr[j - 1][i];
				}
				else
				{
					t[j][i] = t[j - 1][i + (1 << (j - 1))];
					pr[j][i] = pr[j - 1][i + (1 << (j - 1))];
				}
			}
		}
	}
	int get(int l, int r)
	{
		if (l > r)
			swap(l, r);
		int len = r - l + 1, res;
		if (t[f[len]][l] < t[f[len]][r - (1 << f[len]) + 1])
			res = pr[f[len]][l];
		else
			res = pr[f[len]][r - (1 << f[len]) + 1];
		return res;
	}
};