Untitled

#include <bits/stdc++.h>

using namespace std;

void init()
{
	cin.tie(0);
	cin.sync_with_stdio(0);
}

string in;
bitset<26> vis;

struct node
{
	int first_time[26], last_time[26], m;
	node()
	{
		for (int i = 0; i < 26; i++)
			first_time[i] = 1e6, last_time[i] = -1;
		m = 1e6;
	}
};

struct seqTree
{

	vector<node> seg;

	seqTree(int n)
	{
		seg = vector<node>(4 * n + 2);
	}

	node merge(node &left, node &right)
	{
		node ans = node();
		vector<pair<int, int>> l, r;

		int start = -1, j = 0;

		for (int i = 0; i < 26; i++)
		{
			if (right.first_time[i] != 1e6)
			{
				r.push_back({right.first_time[i], i});
				// not in left
				if (left.last_time[i] == -1)
					start = max(start, right.first_time[i]);
			}

			if (left.last_time[i] != -1)
				l.push_back({left.last_time[i], i});

			ans.first_time[i] = min(left.first_time[i], right.first_time[i]);
			ans.last_time[i] = max(left.last_time[i], right.last_time[i]);
		}

		if (l.empty())
		{
			ans.m = right.m;
			return ans;
		}

		if (r.empty())
		{
			ans.m = left.m;
			return ans;
		}

		sort(l.begin(), l.end());
		sort(r.begin(), r.end());
		vis.reset();

		for (int i = 0; i < r.size(); i++)
		{
			if (r[i].first < start)
			{
				vis[r[i].second] = 1;
				continue;
			}

			vis[r[i].second] = 1;
			while (j < l.size() && vis[l[j].second])
				j++;
			if (j < l.size())
				ans.m = min(ans.m, r[i].first - l[j].first + 1);
		}

		// all in right
		if (j >= l.size())
			ans.m = min(ans.m, right.m);

		// all in left
		if (start == -1)
			ans.m = min(ans.m, left.m);

		return ans;
	}

	void bulid(int p, int s, int e)
	{

		if (e == s)
		{
			seg[p].first_time[in[s] - 'a'] = s;
			seg[p].last_time[in[s] - 'a'] = s;
			seg[p].m = 1;
			return;
		}

		bulid(2 * p, s, (s + e) / 2);
		bulid(2 * p + 1, (s + e) / 2 + 1, e);
		seg[p] = merge(seg[2 * p], seg[2 * p + 1]);
	}

	node query(int p, int s, int e, int l, int r)
	{

		if (s > r || e < l)
			return node();

		if (s >= l && e <= r)
			return seg[p];

		node left = query(2 * p, s, (s + e) / 2, l, r);
		node right = query(2 * p + 1, (s + e) / 2 + 1, e, l, r);
		return merge(left, right);
	}
};

int main()
{
	init();
	// freopen("t.text", "r", stdin);
	// freopen("o.text", "w", stdout);

	int n, q, l, r;

	cin >> n >> in;

	in = "1" + in;
	seqTree seg(in.size());
	seg.bulid(1, 1, in.size());

	cin >> q;

	while (q--)
	{
		cin >> l >> r;

		cout << seg.query(1, 1, in.size(), l, r).m << "\n";
	}

	return 0;
}