Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import numpy as np

n = int(input())
p = list(map(int,input().split()))
q = [(v,i) for i,v in enumerate(p)]
q.sort(reverse=True)
flg = np.array([-1,-1,n,n])
ans = 0

for v,i in q:
    if flg.size==0:
        flg = np.append(flg,i)
        continue
    else:
        flg_arr = np.array(flg)
        flg_low = flg_arr[flg_arr<i]
        flg_upp = flg_arr[flg_arr>i]
        ans += v*(  (flg_low[-1]-flg_low[-2])*(flg_upp[0]-i)+
                    (flg_upp[1]-flg_upp[0])*(i-flg_low[-1]))
        flg = np.append(flg,i)
        flg = np.sort(flg)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
N=int(input())
p=list(map(int,input().split()))
LL = [0] + [i for i in range(N+1)]
RR = [i+1 for i in range(N+1)] + [N+1]
E = [(v, i+1) for i, v in enumerate(p)]
E.sort()
ans=0
for v, i in E:
  r0 = RR[i]
  r1 = RR[r0]
  l0 = LL[i]
  l1 = LL[l0]
  RR[l0] = r0
  LL[r0] = l0

  ans += ((r1 - r0)*(i-l0)+(r0-i)*(l0 - l1))*v

print(ans)
### BUGGY CODE ###

A, B, K = map(int, input().split())

while(K>0):
    if A == 0 and B == 0:
        break
    if A > 0:
        A -= 1
        K -= 1
        continue
    if B > 0:
        B -= 1
        K -= 1
        continue

print(A, B)

### FIXED CODE ###

A, B, K = map(int, input().split())

if A == K:
    print(0, B)
elif A > K:
    print(A-K, B)
elif K > A:
    K -= A
    A = 0
    if B == K:
        print(A, 0)
    elif K > B:
        print(A, 0)
    elif B > K:
        print(A, B-K)
### BUGGY CODE ###

def popcount(x):
    return bin(x).count("1")

N,X = open(0).read().split()
N = int(N)
X = int(X, 2)

p = popcount(X)
if p == 0:
    xi = xd = 0
elif p == 1:
    xi = X % 2
    xd = 0
else:
    xi = X % (p + 1)
    xd = X % (p - 1)

for i in range(0, N):
    k = 1 << (N - 1 - i)
    x = X ^ k
    if x == 0:
        print(0)
        continue

    if x > X:
        pi = p + 1
        x = (xi + k) % pi
    else:
        pd = p - 1
        x = (xd - k) % pd
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)


### FIXED CODE ###

def popcount(x):
    return bin(x).count("1")

N, X = open(0).read().split()
N = int(N)
XS = list(X)
X = int(X, 2)

p = popcount(X)
xi = X % (p + 1)
if p == 1:
    xd = 0
else:
    xd = X % (p - 1)

for i in range(N):
    if XS[i] == "1":
        if p == 1:
            print(0)
            continue
        else:
            k = pow(2, N - 1 - i, p - 1)
            x = (xd - k) % (p - 1)
    else:
        k = pow(2, N - 1 - i, p + 1)
        x = (xi + k) % (p + 1)
    ans = 1
    while x != 0:
        x %= popcount(x)
        ans += 1
    print(ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,d=LI()
  l1=[LI() for _ in range(h)]
  q=I()
  l2=[LI() for _ in range(q)]

  ans=[]
  _x=_y=0
  for a,b in l2:
    _ans=0
    ff=True
    f1=f2=False
    while True:
      for i,x in enumerate(l1):
        for j,y in enumerate(x):
          if a==y:
            if b==a:
              if ff:
                ff=False
              else:
                _ans+=abs(_x-i)+abs(_y-j)
              ans.append(_ans)
              f1=f2=True
              break
            else:
              if ff:
                ff=False
              else:
                _ans+=abs(_x-i)+abs(_y-j)
              _x=i
              _y=j
              a+=d
        if f1:
          break
      if f2:
        break

  for x in ans:
    print(x)

main()
# print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w,d=LI()
  l=[LI() for _ in range(h)]

  q=I()
  ql=[LI() for _ in range(q)]

  dic={}
  for i in range(h):
    for j in range(w):
      x=l[i][j]
      dic[x]=(i+1,j+1)

  n=h*w
  to_last_distance=[0]*n
  for i in range(1,n+1)[::-1]:
    if i+d<=n:
      i_y,i_x=dic[i]
      ipd_y,ipd_x=dic[i+d]
      to_last_distance[i-1]=to_last_distance[i+d-1]
      to_last_distance[i-1]+=(abs(i_y-ipd_y)+abs(i_x-ipd_x))

  # print(to_last_distance)

  ans=[]
  for st,ed in ql:
    ans.append(to_last_distance[st-1]-to_last_distance[ed-1])

  for x in ans:
    print(x)

main()
# print(main())
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
for i in range(n):
  if k-(q-a.count(i+1))>0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[0]*n
for i in range(q):
  a[int(input())-1]+=1
for i in range(n):
  if k-(q-a[i])>0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import numpy as np

n, t = map(int, input().split())
a = list(map(int, input().split()))

d = 0
c = 1

m = 0
while m < n - 1:
    y = np.max(a[m:])
    i = a.index(y)
    if i == m:
        m += 1
        continue
    x = np.min(a[m:i])
    if y - x == d:
        c += 1
    elif y - x > d:
        d = y - x
        c = 1
    m = i + 1

print(c)




### FIXED CODE ###

n, t = map(int, input().split())
a = list(map(int, input().split()))

m = a[0]
d = 0
c = 1

for i in range(1, n):
    if a[i] - m > d:
        d = a[i] - m
        c = 1
    elif a[i] - m == d:
        c += 1
    elif a[i] < m:
        m = a[i]

print(c)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n, m, p = map(int, input().split())
edge = []
edge_inv = [[] for _ in range(n)]
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a, b, -c+p))
    edge_inv[b].append(a)


visited = [0] * n
def dfs(v):
    for u in edge_inv[v]:
        if visited[u] == 0:
            visited[u] = 1
            dfs(u)

visited[n-1] = 1
dfs(n-1)
target_nodes = [i for i in range(n) if visited[i]]

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    update = False
    for v_from, v_to, cost in edge:
        if v_from not in target_nodes or v_to not in target_nodes:
            continue
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            update = True
            d[v_to] = d[v_from] + cost


if update:
    print(-1)
else:
    print(max(0, -d[n-1]))


### FIXED CODE ###

n, m, p = map(int, input().split())
graph = [[] for _ in range(n)]
edge = []
for i in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append((b, -c+p))
    edge.append((a, b, -c+p))

INF = float('inf')
d = [INF] * n
d[0] = 0
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost

exist = True
for i in range(n):
    for v_from, v_to, cost in edge:
        if d[v_from] != INF and d[v_to] > d[v_from] + cost:
            d[v_to] = d[v_from] + cost
            if v_to == n - 1:
                exist = False

if not exist:
    print(-1)
else:
    print(max(0, -d[n-1]))
### BUGGY CODE ###

from bisect import insort, bisect
N = int(input())
P = list(map(int, input().split()))

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
memo = [I[N-1]]

for p in range(N-1, 0, -1):
    i = I[p-1]
    b = bisect(memo, i)
    l1 = memo[b-1] if b > 0 else -1
    l2 = memo[b-2] if b > 1 else -1
    r1 = memo[b+0] if b < N-p else N
    r2 = memo[b+1] if b < N-p-1 else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))
    insort(memo, i)

print(ans)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))

I = [0] * N
for i in range(N):
    I[P[i]-1] = i

ans = 0
L = [i for i in range(-1, N-1)]
R = [i for i in range(1, N+1)]

for p in range(1,N+1):
    i = I[p-1]

    if R[i] < N:
        L[R[i]] = L[i]
    if L[i] >= 0:
        R[L[i]] = R[i]

    l1 = L[i]
    l2 = L[l1] if l1 >= 0 else -1
    r1 = R[i]
    r2 = R[r1] if r1 < N else N
    ans += p * ((r1-i)*(l1-l2) + (i-l1)*(r2-r1))

print(ans)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

def func1(lst, value):
    return [i for i, x in enumerate(lst) if x == value]
  
temp=1
trace=[1]
circle=[]
for i in range(K):
  temp=A[temp-1]
  ans=func1(trace,temp)
  if len(ans)==1:
    #print(temp)
    #print(trace.index(temp))
    #start=trace.index(temp)
    circle=trace[ans[0]:]
    #print(circle)
    break
  trace.append(temp)
  #print("temp",temp)
#print((K-i)%len(circle)-1)
if len(circle)!=0:
  amari=(K-i)%len(circle)-1
  print(circle[amari])
else:
  print(temp)

### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
 
check=[-1 for i in range(N)]
  
temp=1
circle=[]
for i in range(K):
  temp=A[temp-1]
  if check[temp-1]==-1:
    check[temp-1]=i
  else:
    circle.append(i-check[temp-1])
    #print(circle)
    break
  #print("temp",temp)
#print((K-i)%len(circle)-1)
if len(circle)!=0:
  amari=(K-i)%circle[0]
  temp=1
  for j in range(i+amari):
    temp=A[temp-1] 

print(temp)
### BUGGY CODE ###

import copy
n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

now = 0
while k > 0:
    if k & 1:
        now = a[now]

    a_next = [-1] * n
    for i in range(n):
        a_next[i] = a[a[i]]

    a = copy.copy(a_next)
    k = k >> 1

ans = now + 1
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))

loop = [0]
s = {0}
while a[loop[-1]] not in s:
    s.add(a[loop[-1]])
    loop.append(a[loop[-1]])

idx = loop.index(a[loop[-1]])
# print(idx, loop)

if k < len(loop):
    ans = loop[k] + 1
else:
    ans = loop[(k - idx) % (len(loop) - idx) + idx] + 1
print(ans)
### BUGGY CODE ###

from sys import stdin
il = lambda func=int: list(map(func, stdin.readline().rstrip().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

a, b, x = il()
ans = 0
for i in range(a, b+1):
    if i % x == 0:
        ans = (b-i) // x + 1
        break
print(ans)

### FIXED CODE ###

from sys import stdin
il = lambda func=int: list(map(func, stdin.readline().rstrip().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

a, b, x = il()
A = (a-1) // x + 1
B = b // x + 1
print(B-A)
### BUGGY CODE ###

def add(x, y):
  if dp_list[x][y] == 0:
    dp_list[x][y] = lists[x] + lists[y]
  return dp_list[x][y]


N = int(input())
lists = list(map(lambda x: int(x), input().split()))
dp_list = [[0 for i in range(N)] for j in range(N)]
count = 0

for a in range(len(lists)):
  if(a + 1) >= len(lists):
    break
  for b in range(a + 1, len(lists)):
    if(b + 1) >= len(lists):
      break
    for c in range(b + 1, len(lists)):
      if add(a, b) > lists[c] and add(b, c) > lists[a] and add(a, c) > lists[b]:
        count += 1
            
print(count)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l = list(map(int,input().split()))
l.sort()
 
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
   ans += bisect_left(l,l[i] + l[j]) - j - 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            else:
                count_list[i][j] = max(count_list[i - 1][j], count_list[i][j - 1])

    return count_list[m][n]


# def lcs_better(A, B):
#     cost_history = [None]
#     for ele in B:
#         for index in range(len(cost_history) - 1, -1, -1):
#             # ???????¬??????°????????????????§???¨A??\?????°??????(ele), ????????°?????????
#             found = A.find(ele, cost_history[index])
#             if found != -1:
#                 if index + 1 < len(cost_history):
#                     cost_history[index + 1] = min(cost_history[index + 1], found + 1)
#                 # ??¨???????????°?????¢?????°?????¶?????°????????´???
#                 else:
#                     assert index + 1 == len(cost_history)
#                     cost_history.append(found + 1)
# 
#     return len(cost_history) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs(word_list[k].strip(), word_list[k + 1].strip()))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
input:
3
abcbdab
bdcaba
abc
abc
abc
bc

output:
4
3
2

"""
import sys


def lcs(A, B):
    m, n = len(A), len(B)
    count_list = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                count_list[i][j] = count_list[i - 1][j - 1] + 1
            elif count_list[i - 1][j] >= count_list[i][j - 1]:
                count_list[i][j] = count_list[i - 1][j]
            else:
                count_list[i][j] = count_list[i][j - 1]

    return count_list[m][n]


def lcs_better(A, B):
    costs = [0]
    for c in B:
        for index in range(len(costs) - 1, -1, -1):
            # print(costs, index + 1)
            x_findex_index = A.find(c, costs[index])
            if x_findex_index != -1:
                if index + 1 < len(costs):
                    costs[index + 1] = min(costs[index + 1], x_findex_index + 1)
                else:
                    costs.append(x_findex_index + 1)
    return len(costs) - 1


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    pair_num = int(_input[0])

    word_list = _input[1:]
    # assert len(word_list) == 2 * pair_num
    for k in range(0, len(word_list), 2):
        print(lcs_better(word_list[k].strip(), word_list[k + 1].strip()))
### BUGGY CODE ###

import copy

N = input()
A = input().split()
n = int(N)
Int_A = [int(a) for a in A]

result = [Int_A[0]]
Int_A.remove(Int_A[0])


def check(a, other):
    if len(other) == 1:
        if result[0] == other[0] ^ a:
            print("Yes")
            exit()
        return []

    res = []
    co_other = copy.deepcopy(other)
    for o in other:
        c = a ^ o
        co_other.remove(o)
        if c in co_other:
            res.append(o)
        co_other.append(o)

    return res


def deep_check(depth):

    resp = check(result[depth - 1], Int_A)

    if len(resp) == 0:
        return

    for k in resp:
        result.append(k)
        Int_A.remove(k)
        depth += 1
        deep_check(depth)
        result.remove(k)
        Int_A.append(k)
    depth -= 1
    return


deep_check(1)
print('No')

### FIXED CODE ###

# import copy
#
N = input()
A = input().split()
n = int(N)
Int_A = [int(a) for a in A]

k = 0

for a in Int_A:
    k ^= a

if k == 0:
    print("Yes")
else:
    print("No")


#
# result = [Int_A[0]]
# Int_A.remove(Int_A[0])
#
#
# def check(a):
#     if len(Int_A) == 1:
#         if result[0] == Int_A[0] ^ a:
#             print("Yes")
#             exit()
#         return []
#
#     res = []
#     co_other = copy.deepcopy(Int_A)
#     for o in Int_A:
#         co_other.remove(o)
#         if a ^ o in co_other:
#             res.append(o)
#         co_other.append(o)
#     del co_other
#
#     return res
#
#
# def deep_check(depth):
#
#     resp = check(result[depth - 1])
#
#     if len(resp) == 0:
#         depth -= 1
#         return
#
#     for k in resp:
#         result.append(k)
#         Int_A.remove(k)
#         depth += 1
#         deep_check(depth)
#         result.remove(k)
#         Int_A.append(k)
#     depth -= 1
#     return
#
#
# deep_check(1)
# print('No')
### BUGGY CODE ###

N, K = map(int, input().split())
V = list(map(int, input().split()))

Q = [ [0 for _ in range(N + 2 * K)] for _ in range(K+1) ]

S = K
E = K + N

for i in range(K, K+N):
    Q[0][i] = V[i-K]

def get(i, S, E, hav, yen):

    ans = yen

    if i >= K:
        return yen

    if S < E:    
        for j in range(S,E):
            Q[i+1][j] = Q[i][j]
        nhav = hav.copy()
        w = Q[i][S]
        nhav.append(w)
        ans = max(ans, get(i+1, S+1, E, nhav, yen + w))

        for j in range(S,E):
            Q[i+1][j] = Q[i][j]
        nhav = hav.copy()
        w = Q[i][E-1]
        nhav.append(w)
        ans = max(ans, get(i+1, S, E-1, nhav, yen + w))

    if len(hav) > 0:
        w = min(hav)

        for j in range(S,E):
            Q[i+1][j] = Q[i][j]
        nhav = hav.copy()
        nhav.remove(w)
        Q[i+1][E] = w
        ans = max(ans, get(i+1, S, E+1, nhav, yen - w))

        for j in range(S,E):
            Q[i+1][j] = Q[i][j]
        nhav = hav.copy()
        nhav.remove(w)
        Q[i+1][S-1] = w
        ans = max(ans, get(i+1, S-1, E, nhav, yen - w))
    
    return ans

print(get(0, S, E, [], 0))


### FIXED CODE ###

from collections import deque, _heapq
N, K = map(int, input().split())
V = deque(map(int, input().split()))

class Money:
    def __init__(self):
        self.yen = 0
        self.red = []

    def value(self):
        return self.yen + sum(self.red)

    def add(self, yen):
        if yen >= 0:
            self.yen += yen
        else:
            self.red.append(yen)

    def remove(self, yen):
        if yen >= 0:
            self.yen -= yen
        else:
            self.red.remove(yen)

#mny = Money()
def get(cnt, mny, lstop, rstop):
    ans = mny.value()

    if cnt <= 0:
        return ans

    if len(V) > 0:

        if lstop == 0:
            w = V.popleft()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, lstop, rstop))
            mny.remove(w)
            V.appendleft(w)
        elif lstop > 0:
            lstop -= 1

        if rstop == 0:
            w = V.pop()
            mny.add(w)
            ans = max(ans, get(cnt-1, mny, -1, rstop))
            mny.remove(w)
            V.append(w)

    if len(mny.red) > 0:
        w = min(mny.red)
        mny.red.remove(w)

        V.appendleft(w)
        ans = max(ans, get(cnt-1, mny, -1, -1))
        V.popleft()

        mny.red.append(w)    

    return ans

print(get(K, Money(), 0, 0))
### BUGGY CODE ###

import math
def sieve_advance(n):  #n未満の整数iについてi以下でiを割り切る最小の素数を求める。
    minfactor=[-1]*n
    minfactor[0],minfactor[1]=0,1
    isprime=[True]*n
    isprime[0],isprime[1]=False,False
    limit=int((math.sqrt(n)+2)//1)
    
    for i in range(2,limit):
        if isprime[i]:
            minfactor[i]=i
            for j in range(i**2,n,i):
                isprime[j]=False
                if minfactor[j]==-1:
                    minfactor[j]=i
    
    return minfactor

minfactor=sieve_advance(10**6+1)
def prime_factor(n): #nをminfactorを利用して素因数分解する
    res={}
    while n!=1:
        prime=minfactor[n]
        exp=0
        while minfactor[n]==prime:
            exp+=1
            n//=prime
        res[prime]=exp

    return res

n=int(input())
nums=list(map(int,input().split()))
mod=10**9+7

factor=[[] for _ in range(n)]
lcm={}
for i in range(n):
  num=nums[i]
  factor[i]=prime_factor(num)
  for p in factor[i].keys():
    e=factor[i][p]
    if p in lcm:
      lcm[p]=max(lcm[p],e)
    else:
      lcm[p]=e
#print(lcm)

b=[1]*n
for p in lcm.keys():
  e_lcm=lcm[p]
  for i in range(n):
    if p in factor[i]:
      e_a=factor[i][p]
    else:
      e_a=0
    b[i]*=p**(e_lcm-e_a) 
    b[i]%=mod
    
#print(b)
print(sum(b)%mod)

### FIXED CODE ###

def main():
  def sieve(n):
    prime=[]
    limit=n*0.5
    data=[i+1 for i in range(1,n)]
    p_append=prime.append
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        p_append(p)
        data=[e for e in data if e%p!=0]
        
  prime=sieve(1000)
  import sys
  import numpy as np
  input=sys.stdin.readline
  mod=10**9+7
  
  n=int(input())
  num=list(map(int,input().split()))
  num_copy=np.array(num)
  
  lcm=1
  for p in prime:
    while np.any(num_copy%p==0):
      num_copy[num_copy%p==0]//=p
      lcm *= p
      lcm %= mod
  
  for i in set(num_copy.tolist()):
    lcm *= i
    lcm %= mod
    
  #print(lcm,num)
  ans=0
  for i in range(n):
    ans += lcm * pow(num[i] ,mod-2 ,mod)
    ans %= mod 
    #print(ans)
  print(ans)
  
if  __name__=='__main__':
  main()
### BUGGY CODE ###

n=int(input())
s=list(map(int,input().split()))
s.sort()

cnt=0
for i in range(n-1):
    for j in range(i+1,n):
        if s[i]==s[j]:
            print('NO')
            exit()
        else:
            cnt+=1
if cnt==n*(n-1)//2:            
    print('YES')
        

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
s.sort()

cnt=0
for i in range(n-1):
    if s[i]==s[i+1]:
        print('NO')
        exit()
    else:
        cnt+=1
if cnt==n-1:            
    print('YES')
### BUGGY CODE ###

X = int(input())

for i in range(10**9):
    if i**5 -(X-i)**5 == X:
        print(i, X-i)
        exit()

### FIXED CODE ###

X = int(input())

for i in range(-200, 200):
    for j in range(-200, 200):
        if i**5 -j**5 == X:
            print(i, j)
            exit()
### BUGGY CODE ###

import numpy as np

n, x, y = map(int, input().split())

ans = [0]*n
for i in range(1, n+1):
  for j in range(i, n+1):
    if i <= j:
      ji = j - i
      xi = i - x
      jy = y - j
      l = [ji,  np.abs(xi) + 1 + np.abs(jy)]
      m = min(l)
      ans[m] += 1
      
print(*ans[1:], sep = '\n')


### FIXED CODE ###

n, x, y = map(int, input().split())

ans = [0]*n
for i in range(1, n+1):
  for j in range(i, n+1):
    m = min(j-i,  abs(x-i) + 1 + abs(j-y))
    ans[m] += 1
      
print(*ans[1:], sep = '\n')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
count = 0
res = []

for i in range(N):
    for j in range(N):
        if j == i:
            continue
        elif (A[i] % A[j]) == 0:
            res.append(A[j])
        else:
            continue
        
    else:
        if len(res) == 0:
            count += 1
            
        else:
            res.clear()

print(count)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
M = 10**6 + 1
 
cnt = [0] * M
 
for a in A:
    if cnt[a] != 0:
        cnt[a] += 1
        continue
    for b in range(a, M, a):
        cnt[b] += 1
 
ans = 0
for a in A:
    if cnt[a] == 1:ans += 1
 
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

p = 10**9 +7
ans = [0]*(n+1)
ans[0] = 1
ans[1] = 1
for i in range(1,n):
    if i in a:
        ans[i] = 0
        ans[i+1] = ans[i-1]%p
    else:
        ans[i+1] = (ans[i-1] + ans[i])%p

print(ans[-1])


### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]

p = 10**9 +7
ans = [0]*(n+1)
ans[0] = 1
ans[1] = 1

broken = [0]*(n+1)
for i in a:
    broken[i]= -1

for i in range(1,n):
    if broken[i] == -1:
        ans[i] = 0
        ans[i+1] = ans[i-1]%p
    else:
        ans[i+1] = (ans[i-1] + ans[i])%p

print(ans[-1])
### BUGGY CODE ###

N,Q = (int(x) for x in input().split())
S = list(input())
for i in range(Q):
    ans = 0
    flag = 0
    l,r = (int(x) for x in input().split())
    for j in range(l-1,r):
        if S[j] == 'A':
            flag = 1
        elif S[j] == 'C':
            if flag == 1:
                ans += 1
        else:
            flag = 0
    print(ans)


### FIXED CODE ###

N,Q = (int(x) for x in input().split())
S = list(input())
count = [0 for i in range(N)]
c = 0
for i in range(N-1):
    if S[i] == 'A':
        if S[i+1] == 'C':
            count[i] = c
            c += 1
            i += 1
        elif S[i+1] != 'A':
            count[i] = c
            i += 1 
    count[i] = c
if count[-2] > count[-1]:
    count[-1] = count[-2]

for i in range(Q):
    l,r = (int(x) for x in input().split())
    print(count[r-1]-count[l-1])