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

from sys import stdin

S = input()
Q = int(input())

T_list = []
for q in range(Q):
    T = stdin.readline()[:-1]

    if T == '1':
        S = S[::-1]

    else:
        t, f, c = T.split()

        if f == '1':
            S = c + S
        else:
            S = S + c

print(S) 


### FIXED CODE ###

from sys import stdin

S = input()
Q = int(input())

reverse_flg = False

former_list = []
latter_list = []

for q in range(Q):
    T = stdin.readline()[:-1]

    if T == '1':
        if reverse_flg:
            reverse_flg = False
        else:
            reverse_flg = True
    
    else:
        t, f, c = T.split()
        if (f == '1' and reverse_flg == False) or (f == '2' and reverse_flg == True):
            former_list.append(c)
        else:
            latter_list.append(c)


if reverse_flg:
    latter_list = ''.join(reversed(latter_list))
    former_list = ''.join(former_list)
    S = ''.join(list(reversed(S)))
    S = ''.join([latter_list, S, former_list])

else:
    former_list = ''.join(reversed(former_list))
    latter_list = ''.join(latter_list)
    S = ''.join([former_list, S, latter_list])

print(S)
### BUGGY CODE ###

s=input().split()
t=[int(i) for i in s]
H=t[0]
W=t[1]
while True:
    if H==0:
        break
    else:
        print("#"*W)
        for i in range(H-2):
            print("#"+"."*(W-2)+"#")
        print("#"*W)
        print()


### FIXED CODE ###

while True:
    s=input().split()
    t=[int(i) for i in s]
    H=t[0]
    W=t[1]
    if H==0:
        break
    else:
        print("#"*W)
        for i in range(H-2):
            print("#"+"."*(W-2)+"#")
        print("#"*W)
        print()
### BUGGY CODE ###

S = input()
n = 0
while 'BW' in S:
    n += S.count('BW')
    S = S.replace('BW','WB')
print(n)

### FIXED CODE ###

S = input()
n = 0
k = 0
m = len(S)
for i in range(m):
    if S[i] == 'B':
        n += m - (i+1) -k
        k += 1
print(n)
### BUGGY CODE ###

# -*- coding:utf-8 -*-
def isPrime(num):
    a = 2
    if num == 1:
        return False

    while num >= a*a:
        if num%a == 0:
            return False
        a += 1

    return True

if __name__ == '__main__':
    q = int(input())
    a = []
    b = {}
    minNum, maxNum = (float('inf'), float('-inf'))
    for tmp in range(q):
        l, r = map(int, input().split())
        minNum = min(minNum, l)
        maxNum = max(maxNum, r)
        a.append((l,r))

    for tmp in range(minNum, maxNum+1):
        factor = (tmp+1)/2
        if isPrime(tmp) and factor == int(factor) and isPrime(factor):
            b[tmp] = 1
        else:
            b[tmp] = 0

    for tmp in a:
        ans = 0
        for tmp2 in range(tmp[0], tmp[1]+1):
            if b[tmp2] == 1:
                ans += 1
        print(ans)

### FIXED CODE ###

# -*- coding:utf-8 -*-
def isPrime(num):
    a = 2
    if num == 1:
        return False

    while num >= a*a:
        if num%a == 0:
            return False
        a += 1

    return True

if __name__ == '__main__':
    q = int(input())
    a = []
    b = {}
    c = []
    for tmp in range(q):
        l, r = map(int, input().split())
        a.append((l,r))

    for tmp in range(1, (10**5)+1):
        factor = (tmp+1)/2
        if isPrime(tmp) and factor == int(factor) and isPrime(factor):
            b[tmp] = 1
        else:
            b[tmp] = 0
    
    c.append(b[1])
    for tmp in range(2,(10**5)+1):
        if b[tmp]:
            c.append(c[len(c)-1]+1)
        else:
            c.append(c[len(c)-1])

    for tmp in a:
        threshold = tmp[0]-2
        if threshold < 0:
            print(c[tmp[1]-1])
        else:
            print(c[tmp[1]-1]-c[threshold])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict, Counter
hs=[]
ws=[]
hd2=defaultdict(list)
wd2=defaultdict(list)
for i in range(m):
    h0,w0=map(int, input().split())
    hs.append(h0)
    hd2[h0].append(w0)
    ws.append(w0)
    wd2[w0].append(h0)

hd=Counter(hs)
wd=Counter(ws)
hmax=max(hd.values())
wmax=max(wd.values())
max_h_list = [kv[0] for kv in hd.items() if kv[1] == hmax]
max_w_list = [kv[0] for kv in wd.items() if kv[1] == wmax]

ans=float('inf')

if len(max_h_list)>=len(max_w_list):
    for x in max_h_list:
        hlist=hd2[x]
        for y in max_w_list:
            if y in hlist:
                ans=min(ans,1)
            else:
                ans=min(ans,0)
else:
    for x in max_w_list:
        wlist=wd2[x]
        for y in max_h_list:
            if y in wlist:
                ans=min(ans,1)
            else:
                ans=min(ans,0)
print(hmax+wmax-ans)


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
h,w,m=map(int, input().split())
hd=[0 for i in range(h+1)]
wd=[0 for i in range(w+1)]
hw=defaultdict(int)
hmax=0
wmax=0
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hmax=max(hmax,hd[h0])
    wd[w0]+=1
    wmax=max(wmax,wd[w0])
    hw[(h0,w0)]+=1

max_h_list=[]
max_w_list=[]
for k in range(h+1):
    if hd[k]==hmax:
        max_h_list.append(k)

for k in range(w+1):
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break
print(hmax+wmax-ans)
### BUGGY CODE ###

N=int(input())
A=[]
A=list(map(int,input().split()))
L=10**18
S=1
for i in range(N):
    S=S*A[i]
if S<=L:
    print(S)
else:
    print("-1")


### FIXED CODE ###

N=int(input())
A=[]
A=list(map(int,input().split()))
A.sort(reverse=True)
L=10**18
S=1
if A[N-1]==0:
    print("0")
else:
    for i in range(N):
        S=S*A[i]
        if S>L:
            print("-1")
            break
    if S<=L:
        print(S)
### BUGGY CODE ###

n = int(input())
ans = 1

for i in range(1, n + 1):
    ans = ans * i

print(ans % (10 ** 9 + 7))

### FIXED CODE ###

n = int(input())
ans = 1

for i in range(1, n + 1):
    ans = (ans * i % (10 ** 9 + 7))

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

#-*- coding: utf-8 -*-

def knapsack2(items, W):
    N = len(items)
    C = [[0 for _i in xrange(W+1)] for _j in xrange(N+1)]
    for i in range(N+1)[1:]:
        v, w = items[i-1]
        for j in range(W+1)[1:]:
            if j < w:
                C[i][j] = C[i-1][j]
            else:
                C[i][j] = max(C[i-1][j-w]+v, C[i-1][j])

    return C[-1][-1]


def input_str(row):
    res = []
    for _ in xrange(row):
        res.append(raw_input().split())
    return res


N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack2(items, W)

### FIXED CODE ###

import collections
import functools

class memoized(object):
    def __init__(self, func):
       self.func = func
       self.cache = {}

    def __call__(self, *args):
       if not isinstance(args, collections.Hashable):
          return self.func(*args)

       if args in self.cache:
          return self.cache[args]

       else:
          value = self.func(*args)
          self.cache[args] = value
          return value

    def __repr__(self):
       return self.func.__doc__

    def __get__(self, obj, objtype):
       return functools.partial(self.__call__, obj)

def knapsack(items, maxweight):
    @memoized
    def bestvalue(i, j):
        if i == 0: return 0
        value, weight = items[i - 1]
        if weight > j:
            return bestvalue(i - 1, j)
        else:
            return max(bestvalue(i - 1, j),
                       bestvalue(i - 1, j - weight) + value)

    j = maxweight
    result = []
    for i in xrange(len(items), 0, -1):
        if bestvalue(i, j) != bestvalue(i - 1, j):
            result.append(items[i - 1])
            j -= items[i - 1][1]
    result.reverse()
    return bestvalue(len(items), maxweight), result

def input_str(row):
    res = []
    for _ in range(row):
        res.append(raw_input().split())
    return res

N, W = [int(i) for i in raw_input().split()]
wvlist = input_str(N)
items = [(int(v), int(w)) for w, v in wvlist]
print knapsack(items, W)[0]
### BUGGY CODE ###

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

yoko = []
for v in s:
    v.append('-')
    tmp = []
    nc =v[0]
    nn = 0
    for c in v:
        if nc == c:
            nn += 1
            continue
        else:
            if nc == '#':
                tmp.extend([0 for _ in range(nn)])
            else:
                tmp.extend( [nn for _ in range(nn)])
            nc = c
            nn = 1
    yoko.append(tmp)

tate = []
for j in range(w):
    tmp = []
    nc = s[0][j]
    nn = 0
    for i in range(h):
        c = s[i][j]
        if nc == c:
            nn += 1
            continue
        else:
            if nc == '#':
                tmp.extend([0 for _ in range(nn)])
            else:
                tmp.extend( [nn for _ in range(nn)])
            nc = c
            nn = 1
    if nc == '#':
        tmp.extend([0 for _ in range(nn)])
    else:
        tmp.extend( [nn for _ in range(nn)])
    tate.append(tmp)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)


### FIXED CODE ###

h, w = map(int, input().split())
S = [input() for _ in range(h)]

def calc(s):
    res = []
    for v in s:
        v = v + '-'
        tmp = []
        nc = v[0]
        nn = 0
        for c in v:
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        tmp = []
        nc = s[0][j]
        nn = 0
        for i in range(h):
            c = s[i][j]
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        if nc == '#':
            tmp.extend([0 for _ in range(nn)])
        else:
            tmp.extend( [nn for _ in range(nn)])
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)
### BUGGY CODE ###

n = int(input())
nodes = []
id_list = []
output = [None for i in range(n)]
cnt = 0
root = set(range(n))
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    root -= set(li)
    nodes.append(li)
    id_list.append(id)

def rooted_tree(id, depth, parent):
    out = {}
    ind = id_list.index(id)
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[ind]
    if len(nodes[ind]) == 0:
        if depth == 0:
            out['type'] = 'root'
        else:
            out['type'] = 'leaf'
        output[id] = out
        return
    if depth == 0:
        out['type'] = 'root'
    else:
        out['type'] = 'internal node'
    output[id] = out
    for i in (nodes[ind]):
        rooted_tree(i, depth+1, id)

rooted_tree(root.pop(), 0, -1)
for line in output:
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))



### FIXED CODE ###

n = int(input())
nodes = [0 for i in range(n)]
output = [None for i in range(n)]
cnt = 0
root = set(range(n))
for i in range(n):
    id, _, *li = list(map(int, input().split(' ')))
    root -= set(li)
    nodes[id] = li

def rooted_tree(id, depth, parent):
    out = {}
    out['node'] = id
    out['parent'] = parent
    out['depth'] = depth
    out['c'] = nodes[id]
    if depth == 0:
        out['type'] = 'root'
    elif len(nodes[id]) == 0:
        out['type'] = 'leaf'
    else:
        out['type'] = 'internal node'
    output[id] = out
    for i in (nodes[id]):
        rooted_tree(i, depth+1, id)

rooted_tree(root.pop(), 0, -1)
for line in output:
    print("node {}: parent = {}, depth = {}, {}, {}".format(line['node'], line['parent'], line['depth'], line['type'], line['c']))
### BUGGY CODE ###

n = int(input())

dx =[-1, 0, 1]

l = [0]
i = 0

while True:
    for x in l:
        if x == n:
            break
    for j in range(len(l)):
        a = l[0]
        l.pop(l[0])
        for k in range(3):
            l.append(a + dx[k]*(i+1))


print(i)

### FIXED CODE ###

import math
n = int(input())
print(math.ceil((-1+(1+8*n)**(1/2))/2))
### BUGGY CODE ###

from math import sqrt
from math import floor
n = int(input())

for i in range(1, n + 1):
    n2 = floor(sqrt(i))
    ans = 0
    for x in range(1, n2):
        for y in range(1, n2):
            for z in range(1, n2):
                if i == pow(x, 2) + pow(y, 2) + pow(z, 2) + x * y + y * z + z * x:
                    ans += 1
    print(ans)


### FIXED CODE ###

n = int(input())

ans = [0] * n
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            a = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if a >= 1 and a <= n:
                ans[a - 1] += 1

for a in ans:
    print(a)
### BUGGY CODE ###

n, k = map(int, input().split())
s = input()

ss = []
tt = []

if s[0] == '0':
  tt += [0]

c = 1
for i in range(1, n):
  if s[i-1:i+1] == '00':
    c += 1
  if s[i-1:i+1] == '10':
    tt += [c]
    c = 1
  if s[i-1:i+1] == '11':
    c += 1
  if s[i-1:i+1] == '01':
    ss += [c]
    c = 1
if s[n-1] == '0':
  ss += [c]
else:
  tt += [c]

sr = k
tr = k + 1

sl = len(ss)
tl = len(tt)

mm = 0
for i in range(tl):
  try:
    m = sum(ss[i:i+sr]) + sum(tt[i:i+tr])
    if mm < m:
      mm = m
  except:
    pass
print(mm)


### FIXED CODE ###

n, k = map(int, input().split())
s = input()

from itertools import groupby, accumulate

def gen(s):
  if s[:1] == '0':
  	yield 0
  for ke, g in groupby(s):
    yield len(list(g))
  if s[-1:] == '0':
    yield 0


mc = 0
acc = list(accumulate(gen(s)))
r = 2 * k + 1
if len(acc) < r:
  mc = n
else:
  for i in range(0, len(acc)-r+1, 2):
    if i == 0:
      mc = max(mc, acc[i+r-1])
    else:
      mc = max(mc, acc[i+r-1] - acc[i-1])
print(mc)
### BUGGY CODE ###

n,m = map(int,input().split())
alist = list(map(int,input().split()))
for i in range(m):
  alist.sort()
  alist[-1] //= 2
print(sum(alist))

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from math import log

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

table = [[0]*(int(log(a[-1],2))+2) for i in range(n)]

for i in range(n):
    for y in range(int(log(a[-1],2))+2):
        table[i][y] = a[i]//pow(2,y)
        if a[i]//pow(2,y) == 0:
            break

s_table = [[0]*(int(log(a[-1],2))+2) for i in range(n)]
for i in range(n):
    s_table[i][0] = table[i][0]

import heapq
hq = []
heapq.heapify(hq)
h_push = heapq.heappush
h_pop = heapq.heappop

for i in range(n):
    for y in range(1,int(log(a[-1],2))+2):
        s_table[i][y] = table[i][y]-table[i][y-1]
        h_push(hq,table[i][y]-table[i][y-1])
        if table[i][y]-table[i][y-1] == -1:
            break


ans = sum(a)

for i in range(m):
    if not hq:
        print(0)
        exit()
    ans += h_pop(hq)
    
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
SA = sorted(A)

D = []
for _ in range(M):
  B, C = map(int, input().split())
  D += B * [C]
SD = sorted(D, reverse=True)
X = min(N, len(SD))
SD = SD[:X]

for i in range(X):
  if SD[i] > SA[i]:
    SA[i] = SD[i]
print(sum(SA))
  


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
#SA = sorted(A)

D = []
for _ in range(M):
  B, C = map(int, input().split())
  D.append([B, C])

SD = sorted(D, key=lambda x:x[1], reverse=True)

for b, c in SD:
  A += b * [c]
  if len(A) > N*2:
    break

SA = sorted(A, reverse=True)
#X = min(N, len(SD))
#SD = SD[:X]

print(sum(SA[:N]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

def knapsack(i, w) :
    if i == N :
        return 0
    
    M = knapsack(i + 1, w)
    
    if w >= wv[i][0] :
        M = max(M, knapsack(i + 1, w - wv[i][0]) + wv[i][1])
        
    return M
    
print(knapsack(0, W))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

s = [[] for _ in range(4)]
w0 = wv[0][0]
for w, v in wv :
    s[w-w0].append(v)
for i in range(4) :
    s[i].sort(reverse=True)
    s[i] = [0] + s[i]
    for j in range(1, len(s[i])) :
        s[i][j] += s[i][j-1]

M = 0
for i0 in range(len(s[0])) :
    for i1 in range(len(s[1])) :
        for i2 in range(len(s[2])) :
            for i3 in range(len(s[3])) :
                if i0*w0+i1*(w0+1)+i2*(w0+2)+i3*(w0+3) <= W :
                    M = max(M, s[0][i0]+s[1][i1]+s[2][i2]+s[3][i3])
                    
print(M)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
res = 1
for i in range(n):
  res = a_list[i]*res
if res > 1000000000000000000:
    print(-1)
else:
  print(res)

### FIXED CODE ###

n = int(input())
a_list = list(map(int, input().split()))
a_list.sort(reverse=True)
res = 1
flag0 = False
if 0 in a_list:
  res = 0
else:
  for i in range(n):
    res = a_list[i]*res
    if res > 1000000000000000000:
      res = -1
      break

print(res)
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    query = list(input().split())
    if(int(query[0]) == 1):
        s = s[::-1]
    elif(int(query[0]) == 2):
        txt = ''.join(query[2:])
        if(int(query[1]) == 1):
            s = txt + s
        elif (int(query[1]) == 2):
            s += txt

print(s)

### FIXED CODE ###

from collections import deque

s = deque(list(input()))
q = int(input())

rev = True

for i in range(q):
    q = list(input().split())
    if(int(q[0]) == 1):
        rev = rev ^ True
    else:
        n = int(q[1])
        if((n == 1 and rev) or (n == 2 and not rev)):
            s.appendleft(q[2])
        else:
            s.append(q[2])


txt = ''
if rev:
    txt = ''.join(s)
else:
    while not(not s):
        txt += s.pop()

print(txt)
### BUGGY CODE ###

N = int(input())
a  = list(map(int, input().split()))
begin = -1
max = N+1

for i in range(1,N+1):
    try:
        begin = a.index(i)
    except ValueError:
        break
    
    a = a[begin+1:]
    max = i

print(N-max)

### FIXED CODE ###

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

j = 1
for i in range(N):
    if j == a[i]:
        j += 1

if j == 1:
    print(-1)
else:
    print(N-j+1)
### BUGGY CODE ###

# 最小公倍数(ユーグリッド互除法)
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd( b, a % b)

K = int(input()) +1

# データパターンを求める式
ans = 0
for h in range(1, K):
  for i in range(1, K):
    for j in range(1, K):
      # 最小公倍数算出
      ans += gcd(h,gcd(i,j))

print(ans)

### FIXED CODE ###

# 最小公倍数(ユーグリッド互除法)
def gcd(a,b):
  if b == 0:
    return a
  else:
    return gcd( b, a % b)

K = int(input()) + 1
mydict = {}

# データパターンを求める式
ans = 0
for h in range(1, K):
  ans += gcd(h,gcd(h,h))

  for i in range(h+1, K):
    ans += (gcd(h,gcd(h,i)) * 3)
    ans += (gcd(h,gcd(i,i)) * 3)

    for j in range(i+1, K):
      ans += (gcd(h,gcd(i,j)) * 6)

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

n,m=map(int,input().split())
maxi=0
cnt=1
while cnt<=m:
    if m%cnt==0:
        if m//cnt>=n:
            maxi=cnt
            cnt+=1
        else:
            cnt+=1     
    else:
        cnt+=1       
print(maxi)

### FIXED CODE ###

n,m=map(int,input().split())
maxi=0
import math
num=math.sqrt(m)
nums=math.floor(num)

for i in range(1,nums+1):
    if m%i==0:
        number1=i
        number2=m//i
        #二つの約数について比べる
        #number1<number2
        #m//number1>m//number2
        if m//number1>=n and m//number2>=n:
            maxi=max(number2,maxi)
        elif m//number1>=n and m//number2<n:
            maxi=max(maxi,number1)
        
    else:
        continue
print(maxi)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    M = max(a)
    p = len(format(M, 'b'))
    l = [[0 for _ in range(n)] for _ in range(p)]
    ans = 0
    for i in range(n):
        a_s = format(a[i], '0' + str(p) + 'b')
        for c in range(p):
            l[c][i] = int(a_s[c])
    for i in range(p):
        c1 = sum(l[i])
        ans += (2**(p - i - 1)) * c1 * (n - c1)
        ans %= (10**9 + 7)
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    a = [int(_) for _ in input().split()]
    M = max(a)
    p = len(format(M, 'b'))
    l = [0 for _ in range(p)]
    ans = 0
    for i in range(n):
        a_s = format(a[i], '0' + str(p) + 'b')
        for c in range(p):
            if a_s[c] == '1':
                l[c] += 1
    for i in range(p):
        c1 = l[i]
        ans += (2**(p - i - 1)) * c1 * (n - c1)
        ans %= (10**9 + 7)
    print(ans)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
p = list(map(int, input().split()))

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    v = d[pos]
    vacant[pos] = True
    q = [(v, pos)]
    while q:
        v,pos = q.pop()
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>v:
                d[ppos] = v
                nv = v+1 if not vacant[ppos] else v
                q.append((nv, ppos))
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
p = list(map(int, input().split()))

d = [None] * (n**2)
for i in range(n):
    for j in range(n):
        d[i*n+j] = min(i, n-1-i, j, n-1-j)
vacant = [False] * (n**2)

ans = 0
for pos in p:
    pos -= 1
    ans += d[pos]
    vacant[pos] = True
    q = [pos]
    while q:
        pos = q.pop()
        tmp = not vacant[pos]
#         for diff in (-1, 1, -n, n):
#             ppos = diff+pos
#             if ppos<0 or ppos>=n*n:
#                 continue
#             if d[ppos]>d[pos]+tmp:
#                 d[ppos] = d[pos] + tmp
#                 q.append(ppos)
        if pos+n<n*n:
            ppos = pos + n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-n>=0:
            ppos = pos - n
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos+1<n*n:
            ppos = pos + 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
        if pos-1>=0:
            ppos = pos - 1
            if d[ppos]>d[pos]+tmp:
                d[ppos] = d[pos] + tmp
                q.append(ppos)
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for i in range(Q):
  l, r = map(int, input().split())
  print (S[l-1:r].count("AC"))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [0] * N
for i in range(1,N):
  cnt[i] = cnt[i-1]
  if S[i-1:i+1] == "AC":
    cnt[i] += 1
for i in range(Q):
  r, l = map(int, input().split())
  print (cnt[l-1] - cnt[r-1])