F. Queries on Distincts
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Given a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters.

You have to answer $$$q$$$ queries of the following form:

— "$$$l$$$ $$$r$$$": Find the minimum size of substring $$$s[i \dots j]$$$ ($$$l \le i \le j \le r$$$) such that the number of distinct characters in $$$s[i \dots j]$$$ is equal to the number of distinct characters in $$$s[l \dots r]$$$.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the string.

The second line of the input contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters.

The third line of the input contains a single integer $$$q$$$ ($$$1 \le q \le 10^5$$$) — the number of queries.

Each of the following $$$q$$$ lines of the input consists of two space-separated integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$).

Output

Output $$$q$$$ lines, the $$$i$$$-th of which contains a single integer — the answer to the $$$i$$$-th query.

Example
Input
3
aba
1
1 3
Output
2