#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <utility>
#include <numeric>

using namespace std;

const int INF = 2E9;
const uint64_t MOD = 1E9 + 7;

int partition(vector<int> &a)
{
	int x = a.back();
	int id = -1;

	for (int i = 0; i < a.size() - 1; i++)
	{
		if (a.at(i) <= x)
		{
			id++;
			swap(a.at(i), a.at(id));
		}
	}
	swap(a.at(id + 1), a.back());

	return id + 1;
}

int main()
{
	int n;
	cin >> n;

	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a.at(i);
	}

	int p = partition(a);

	for (int i = 0; i < n; i++)
	{
		cout << (i == 0 ? "" : " ");
		if (i == p)
		{
			cout << "[" << a.at(i) << "]";
		}
		else
		{
			cout << a.at(i);
		}
	}

	cout << endl;
}

#include <bits/stdc++.h>
using namespace std;

struct StQuery
{
  StQuery() : m_nLeft(0), m_nRigt(0) { }

  int m_nLeft;
  int m_nRigt;
};

void input(string& rsStr, vector<StQuery>& rvoQuery)
{
  int nStrSiz, nQuerySiz;
  cin >> nStrSiz >> nQuerySiz;
  rvoQuery.resize(nQuerySiz);

  cin >> rsStr;
  
  for (StQuery& roQuery : rvoQuery)
    cin >> roQuery.m_nLeft >> roQuery.m_nRigt;
}

void calcSubStrACCnt(string sStr, const vector<StQuery>& cnrvoQuery)
{
  vector<int> vnCumlSum(sStr.size() + 1);      // 累積和

  //vnCumlSum_ix 0 1 2 3 4 5 6 7 8
  //sStr_pos      1 2 3 4 5 6 7 8
  //sStr          A C A C T A C G
  //sStr_ix       0 1 2 3 4 5 6 7
  for (int nBgn = 0; nBgn < vnCumlSum.size() - 1; nBgn++)
  {
    vnCumlSum[ nBgn + 2 ] = vnCumlSum[ nBgn + 1 ];
    if (sStr[nBgn] == 'A' && sStr[nBgn + 1] == 'C')
      vnCumlSum[ nBgn + 2 ]++;
  }

 for (int i = 0; i < cnrvoQuery.size(); i++)
  {
    cout << vnCumlSum[ cnrvoQuery[i].m_nRigt ] - vnCumlSum[ cnrvoQuery[i].m_nLeft ];
    cout << endl; 
  }
}
 
int main()
{
  string sStr;
  vector<StQuery> voQuery;

  input(sStr, voQuery);
  calcSubStrACCnt(sStr, voQuery);

  return 0;
}