//?

// https://ac.nowcoder.com/acm/contest/32708/E

#include "stdafx.h"

?

#include <algorithm>

#include <iostream>

#include <cstring>

?using namespace std;

const int N = 1E5 + 100;

int n, m, block;

int arr[N]={

0,1, 2, 3,4, 1,2,3

};

/*? 莫隊算法 (Mo's Algorithm)

For query 4.4,? repeat=3

123.....

....123

1...23

12....3

For query 3.3.??repeat=2

12....3

1...23

....123

*/

long long res[N];

pair<int, int> cnt[N];

struct Mo {

? ? int L, r, idx;

? ? bool operator < (const Mo &rhs) const {

? ? ? ? if (L / block == rhs.L? / block) {

? ? ? ? ? ? return r < rhs.r;

? ? ? ? }

? ? ? ? return L? / block < rhs.L? / block;

? ? }

};

Mo qry[N];

int Q[N][2]={

1, 1,

3, 3,

2 ,3,

2 ,4,

1 ,3,

1 ,4,

4,4

};

int main() {

? ? ? n=7;m=7;

? ? /*

cin >> n;

? ? for (int i = 1; i <= n; i++) {

? ? ? ? cin >> arr[i];

? ? }*

? ? cin >> m;

? ? for (int i = 1; i <= m; i++) {

? ? ? ? cin >> qry[i].l >> qry[i].r;

? ? ? ? qry[i].i = i;

? ? }*/

for (int i = 1; i <= m; i++) {

? ? ? ? ?qry[i].L =Q[i-1][0]; qry[i].r=Q[i-1][1];

? ? ? ? qry[i].idx = i;

}

? ? block = sqrt(n); ?

cout<<block<<endl;

? ?sort(qry + 1, qry + 1 + m);

for (int i = 1; i <= m; i++) cout<<qry[i].idx<<"? ?";

cout<<endl;

? ? int left = 1, r = n;

??

for (int i = 1; i <= n; i++) {

? ? ? ? cout<<cnt[arr[i]].first<<",? sec="<<cnt[arr[i]].second <<endl;

? ? }

? ? int? repeat = 0;

? ? for (int i = 1; i <= m; i++) {

? ? ? ? while (left < qry[i].L ) {

? ? ? ? ? ? repeat += cnt[arr[left]].second;

? ? ? ? ? ? cnt[arr[left++]].first += 1;

? ? ? ? }

cout <<" repeat="<<repeat<<" i="<<i<<" left="<<left<<" r="<<r<<endl;

? ? ? ? while (left > qry[i].L ) {

? ? ? ? ? ? cnt[arr[--left]].first -= 1;

? ? ? ? ? ? repeat -= cnt[arr[left]].second;

? ? ? ? }

cout <<" repeat="<<repeat<<" i="<<i<<" left="<<left<<" r="<<r<<endl;

? ? ? ? while (r < qry[i].r) {

? ? ? ? ? ? cnt[arr[++r]].second -= 1;

? ? ? ? ? ? repeat -= cnt[arr[r]].first;

? ? ? ? }

cout <<" repeat="<<repeat<<" i="<<i<<" left="<<left<<" r="<<r<<endl;

? ? ? ? while (r > qry[i].r) {

? ? ? ? ? ? repeat += cnt[arr[r]].first;

? ? ? ? ? ? cnt[arr[r--]].second += 1;

? ? ? ? }

cout <<" repeat="<<repeat<<" i="<<i<<" left="<<left<<" r="<<r<<endl;

cout <<repeat<<" i="<<i<<" r="<<r<<" L="<<qry[i].L<<" qry[i].r="<<qry[i].r<<"? qry[i].idx= "<<qry[i].idx<<endl;

for (int ii = 1; ii <= n; ii++)?

{

cout<<cnt[arr[ii]].first<<",? sec="<<cnt[arr[ii]].second <<endl;

}

? ? ? ? res[qry[i].idx] = 1LL * qry[i].L? * (n - qry[i].r + 1) - repeat;

cout<<res[qry[i].idx]<<"=res[qry[i].idx]"<<endl;

? ? }

? ? for (int i = 1; i <= m; i++) {

? ? ? ? cout << res[i] << endl;

? ? }

? ? return 0;

}