#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(int i=n; i>-1; --i)
#define ALL(a) (a).begin(),(a).end()
#define FILL(a,n,x); REP(i,(n)){ (a)[i]=(x); }
#define CINA(a,n); REP(i,(n)){ cin >> (a)[i]; }
#define FILL2(a,n,m,x); REP(i,(n)){ REP(j,(m)){(a)[i][j]=(x);} }
#define CINA2(a,n,m); REP(i,(n)){ REP(j,(m)){cin >> (a)[i][j];} }
#define Liny "Yes\n"
#define Linn "No\n"
#define LINY "YES\n"
#define LINN "NO\n"

//cout << setfill('0') << right << setw(4) << 12; // "0012"
int keta(ll x){ if(x<10){return 1;} else{return keta(x/10) + 1;}}
int keta_wa(ll x){ if(x<10){return x;} else{return keta_wa(x/10) + x%10;} }
int ctoi(char c){ return ( (c>='0' && c<='9')? c - '0': 0 );}
int __stoi(string s){ return atoi(s.c_str()); }
ll sum(ll a[],ll N){ return accumulate(a,a+N,0LL);}
ll gcd(ll a,ll b){if(a<b)swap(a,b); return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){if(a<b){swap(a,b);} return a/gcd(a,b)*b;}
template<class T> void chmax(T& a, T b){ if(a<b){a=b;} }
template<class T> void chmin(T& a, T b){ if(a>b){a=b;} }
template<class T> bool isIn(T a,vector<T> v){ for(T x:v){ if(a==x){return true;}} return false;}
string strReplace(string s,string target, string replacement){
    if (!target.empty()) {
      std::string::size_type pos = 0;
      while ((pos = s.find(target, pos)) != std::string::npos) {
        s.replace(pos, target.length(), replacement);
        pos += replacement.length();
      }
    }
    return s;
}
const ll MOD = 1e9+7;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair

bool DEBUG = 0;

template<class T> void dprint(T s){
  if(DEBUG){ cout << s << "\n"; }
}


int main(int argc,char* argv[]){
  if(argc>1 && argv[1][0]=='D'){ DEBUG=1;}
  dprint("start");

  ll N; cin>>N;
  ll a[N]; CINA(a,N); reverse(a,a+N);
  vector<ll> v;
  v.push_back(a[0]);
  for(int i=1;i<N;++i){
    int m = v.size();
    if(a[i]>=v[m-1]){
      v.push_back(a[i]);
    }else{
      auto x = upper_bound(ALL(v),a[i]);
      while(*x==a[i]){
        ++x;
      }
      *x = a[i];
    }
  }
  if(DEBUG){ for(auto x:v){ cout << x << " ";} cout << "\n"; }
  cout << v.size() << "\n";
}
#include <bits/stdc++.h>
#include<math.h>
#include<algorithm> 
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
#define INF 1e18
#define mod 1000000007

int main () {
    int n, q ;
    string s ;
    cin >> n >> q ;
    cin >> s ; 
    vector<int> l (q), r(q) ;
    rep(i, q){
        cin >> l[i] >> r[i] ;
        l[i]-- ;
        r[i]-- ;
    }
    vector<int> num (n) ;
    rep(i, n - 1){
        if(s[i] == 'A' && s[i + 1] == 'C'){
            num[i + 1]++ ; 
        }
    }
    for(int i = 1 ; i < n ; i++){
        num[i] += num[i - 1] ;
    }
    vector<int> ans ;
    rep(i, q){
        ans.push_back(num[r[i]] - num[l[i]]) ;
    }
    rep(i, q){
        cout << ans[i] << endl ; 
    }
}

