Untitled

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i , st , ed) for(int i = st; i < ed; i++)
#define f first
#define s second
#define all(v) v.begin() , v.end()
#ifndef ONLINE_JUDGE 
#define debug(x) cerr << #x << ": " << x << '\n';
#else
#define debug(x)
#endif
const int N = 1e5 + 200 , inf = 1e9;
template<class T = int>
struct Sparetable{
    vector<vector<T>> mx;
    int n , LOG;
    void init(vector<T> &a){
        this-> n = (int) a.size();
        this->LOG = 0;
        int size = 1;
        while(size <= n) size *= 2 , LOG++;
        mx.assign(n , vector<T>(LOG));
        for (int i = 0; i < n; i++)mx[i][0] = a[i];
        for (int j = 1; (1 << j) <= n; j++){
            for (int i = 0; (i + (1 << j) - 1) < n; i++){
                mx[i][j] = merge(mx[i][j - 1] , mx[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    T merge(T a , T b){
        return a | b; // change the operation
    }
    T qry(int l, int r){
        int len = r - l + 1;
        int j = 31 - __builtin_clz(len);
        T res = merge(mx[l][j] , mx[r - (1 << j) + 1][j]);
        return __builtin_popcountll(res); // determine what you want to return 
    }
};

int tree[27][4 * N] , n;
int qry(int tree[] , int lx , int rx , int x = 0, int l = 0, int r = n){
    if(l >= lx && r <= rx) return tree[x];
    if(r <= lx || l >= rx)  return inf;
    int mid = (l + r) / 2;
    int q1 = qry(tree , lx , rx , 2 * x + 1 , l , mid);
    int q2 = qry(tree , lx , rx , 2 * x + 2 , mid , r);
    return min(q1 , q2);
}
void upd(int tree[] , int i , int v , int x = 0, int l = 0, int r = n){
    if(r - l == 1){ tree[x] = min(tree[x] , v); return; }
    int mid = (l + r) / 2;
    if(i < mid) upd(tree , i , v , 2 * x + 1 , l , mid);
    else upd(tree , i , v , 2 * x + 2 , mid , r);
    tree[x] = min(tree[2 * x + 1] , tree[2 * x + 2]);
}
void init(){
    for(int i = 0; i < 27; ++i){
        for(int j = 0; j <= 4 * n; ++j) tree[i][j] = inf;
    }
}
int main(){
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    cin >> n;
    string s; cin >> s;
    vector<pair<int,int>> query[n];
    int q; cin >> q;
    int ans[q];
    for(int i = 0; i < q; ++i){
        int l , r; cin >> l >> r;
        --l; --r;
        query[r].emplace_back(l , i);
    }

    vector<ll> a(n);
    for(int i = 0; i < n; ++i) a[i] = ( 1 << (s[i] - 'a') );
    Sparetable<ll> spt; spt.init(a);
    init();
    int last[n][27];
    memset(last , -1 , sizeof last);
    for(int i = 0; i < n; ++i){
        int tar = spt.qry(0 , i);
        while(tar){
            int lo = 0 , hi = i , mid;
            while(lo <  hi){
                mid = lo + (hi - lo + 1) / 2;
                if( spt.qry(mid , i) >= tar ) lo = mid;
                else hi = mid - 1;
            }
            last[i][tar] = lo;
            --tar;
        }
    }


    
    for(int r = 0; r < n; ++r){
        for(int i = 1; i <= 26; ++i) if(~last[r][i]){
            int l = last[r][i];
            upd(tree[i] , l , r - l + 1);
        }
        for(auto &[l , i] : query[r]){
            int tar = spt.qry(l , r);
            ans[i] = qry(tree[tar] , l , r + 1);
        }
    }
    for(int i = 0; i < q; ++i)
        cout << ans[i] << ' ';
}