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

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
DIRC = [(-1, 0), (0, 1), (1, 0), (0, -1)]
exist = [1]*(n**2)


def bfs(init_v):
    next_v = deque([divmod(init_v, n)])
    exist[init_v] = 0
    while next_v:
        i, j = next_v.popleft()
        for di, dj in DIRC:
            x, y = i+di, j+dj
            if x < 0 or y < 0 or n <= x or n <= y:
                continue
            c = cost[i*n+j]+exist[i*n+j]
            if cost[x*n+y] <= c:
                continue
            cost[x*n+y] = c
            next_v.append((x, y))


ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(lambda x: int(x)-1, input().split()))
cost = [min(i, n-1-i, j, n-1-j) for i in range(n) for j in range(n)]
exist = [1]*(n**2)


def to_idx(p):
    return divmod(p, n)


def to_v(i, j):
    return i*n+j


def bfs(init_v):
    next_v = deque([init_v])
    exist[init_v] = 0
    while next_v:
        v = next_v.popleft()
        i, j = to_idx(v)
        if 0 < i:
            v2 = v-n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if i < n-1:
            v2 = v+n
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if 0 < j:
            v2 = v-1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

        if j < n-1:
            v2 = v+1
            if cost[v2] > cost[v]+exist[v]:
                cost[v2] = cost[v]+exist[v]
                next_v.append(v2)

ans = 0
for p in Ps:
    ans += cost[p]
    bfs(p)
print(ans)
### BUGGY CODE ###

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
INF = float('inf')

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0, 0), (w[0], v[0])]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    dp[u] = dp[parent].copy()
    for ww, vv in dp[parent]:
        dp[u].append((ww + w[u], vv + v[u]))
    dp[u].sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(dp[u])):
        if dp[u][i][0] > max_l:
            break
        if dp[u][tail][0] == dp[u][i][0]:
            dp[u][tail] = dp[u][i]
        elif dp[u][tail][1] < dp[u][i][1]:
            tail += 1
            dp[u][tail] = dp[u][i]
    del dp[u][tail + 1:]

def solve(u, l):
    if u < len(dp):
        x = bisect.bisect_right(dp[u], (l, INF)) - 1
        return dp[u][x][1]

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

### FIXED CODE ###

# D - Knapsack Queries on a tree

from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = map(int, readline().split())

max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1

# dp table (for some amount)
dp = [None] * min(n, 2 ** 12)

# dp[vertex] = list of (weight, value)
dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend(x + (w[u] << vshift) + v[u] for x in dp[parent]
              if (x >> vshift) + w[u] <= max_l)
    ls.sort()

    # remove unnecessary entries
    tail = 0
    for i in range(1, len(ls)):
        if (ls[tail] >> vshift) == (ls[i] >> vshift):
            ls[tail] = ls[i]
        elif (ls[tail] & mask) < (ls[i] & mask):
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l << vshift) + mask) - 1
        return dp[u][x] & mask

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #C
    #input
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
     
    #output
    #A[i]の電球は i-A[i] から i+A[i]までを照らす。
    import numpy as np  
    K = min(K, 42)
    for _ in range(K):
        dp = np.zeros(N, int)
        for i in range(N):
            p = max(0, i-A[i])
            dp[p] += 1
            if i+A[i]+1 <= N-1:
                dp[i+A[i]+1] -= 1
        dp = np.cumsum(dp)
        A = dp
     
    print(" ".join(repr(d) for d in dp))    

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()


### FIXED CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #C
    #input
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
     
    #output
    #A[i]の電球は i-A[i] から i+A[i]までを照らす。
    import itertools
    K = min(K, 42)
    for _ in range(K):
        dp = [0]*N
        for i in range(N):
            p = max(0, i-A[i])
            dp[p] += 1
            if i+A[i]+1 <= N-1:
                dp[i+A[i]+1] -= 1
        dp = list(itertools.accumulate(dp))
        A = dp
     
    print(" ".join(repr(d) for d in dp))

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,W=list(map(int,input().split()))
DP=[[0]*(W+1) for i in range(N+1)]
for i in range(1,N+1):
    w,v=list(map(int,input().split()))
    for j in range(W+1):
        if j-w>=0:
            DP[i][j]=max(DP[i-1][j],DP[i-1][j-w]+v)
        else:
            DP[i][j]=max(DP[i-1][j],DP[i][j-1])
print(DP[-1][-1])

### FIXED CODE ###

import numpy as np
N,W=list(map(int,input().split()))
DP=np.zeros(W+1)

for i in range(N):
    w,v=list(map(int,input().split()))
    a=DP[:-w]+v
    b=DP[w:]
    c=np.maximum(a,b)
    DP[w:]=c



print(int(DP[-1]))
# for i in DP:
#     print(i)
### BUGGY CODE ###

def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  x=reversed_num(number[-1])+1
  number.pop()
  if x in number:
    number.remove(x)
    count+=1
print(count)


### FIXED CODE ###

import bisect
def reversed_num(num):
  num_len=len(bin(num))-2
  f=2**num_len-1
  return num^f
n=int(input())
number=list(map(int,input().split()))
number.sort()
count=0
while len(number)>0:
  k=number.pop()
  if len(number)==0:
    break
  if k==int(k):
    x=reversed_num(k)+1
    y=bisect.bisect_left(number,x)
    if x>number[-1]:
      y-=1
    if number[y] ==x:
      number[y]-=0.5
      count+=1
print(count)
### BUGGY CODE ###

import math

K = int(input())
valSum = 0

for A in range(1,K+1):
    for B in range(1,K+1):
        for C in range(1,K+1):
            valSum += math.gcd(math.gcd(A,B),C)

print(valSum)



### FIXED CODE ###

from math import gcd

K = int(input())
valSum = 0

for A in range(1,K+1):
    for B in range(1,K+1):
        for C in range(1,K+1):
            valSum += gcd(gcd(A,B),C)

print(valSum)
### BUGGY CODE ###

def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    mid = 0
    diff = float("inf")
    for i in range(1, n):
        if abs(sum(A[:i]) - sum(A[i:])) <= diff:
            diff = abs(sum(A[:i]) - sum(A[i:]))
            mid = i
    
    front = A[:mid] 
    back =  A[mid:]
    print(abs(sum(front)-sum(back)))
resolve()

### FIXED CODE ###

def resolve():
    n = int(input())
    A = list(map(int, input().split()))

    mid = 0
    diff = float("inf")
    total = sum(A)
    p = 0
    # print(total)
    for i in range(n):
        # print("i:",i, "total:", total, "p:", p, "diff:", diff)
        if abs(total-p) < diff:
            diff = abs(total - p)
            mid = i
        p += A[i]
        total -= A[i]
    front = A[:mid] 
    back =  A[mid:]
    print(abs(sum(front)-sum(back)))
resolve()
### BUGGY CODE ###

# s1 = input()
# len_s = len(s1)
# s2 = s1
# while True:
#     len_1 = len(s2)
#     s2 = s2.replace("01", "").replace("10", "")
#     len_2 = len(s2)
#     if len_1 == len_2:
#         break
#
# print(len_s - len(s2))

s = input()
s2 = s
# for i in range(len(s) // 2, 0, -1):
#     # print("i", i)
#     # print("s2", s2)
#     m1 = "1" * i + "0" * i
#     m2 = "0" * i + "1" * i
#     s2 = s2.replace(m1, "").replace(m2, "")

while True:
    len_1 = len(s2)

    a1 = "000111"
    a2 = "111000"
    if a1 in s2:
        s2 = s2.replace(a1, "")
    if a2 in s2:
        s2 = s2.replace(a2, "")

    a3 = "0011"
    a4 = "1100"
    if a3 in s2:
        s2 = s2.replace(a3, "")
    if a4 in s2:
        s2 = s2.replace(a4, "")

    a5 = "01"
    a6 = "10"
    if a5 in s2:
        s2 = s2.replace(a5, "")
    if a6 in s2:
        s2 = s2.replace(a6, "")

    len_2 = len(s2)
    if len_1 == len_2:
        break

print(len(s) - len_2)


### FIXED CODE ###

s = input()
ans = min(s.count('0'), s.count('1'))
print(ans * 2)
### BUGGY CODE ###

a, b, x = map(int, input().split())

start = a if a >= x else x
end = b
while start <= end:
    if start % x == 0:
        break
    if start == end:
        print(0)
        exit()
    start += 1

result = (end - start) // x + 1
if a == 0:
    result += 1
print(result)


### FIXED CODE ###

a, b, x = map(int, input().split())

start = 0
end = b
if a > x:
    if a % x == 0:
        start = a
    else:
        start = x * (a // x + 1)
else:
    start = x

if start > end:
    result = 0
else:
    result = (end - start) // x + 1
if a == 0:
    result += 1
print(result)
### BUGGY CODE ###

def main():
  from collections import defaultdict
  from heapq import heappush,heappop
  inf=10**12
  n,m,*t=map(int,open(0).read().split())
  edge=defaultdict(list)
  used,d={},{}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    x,y=a+n*c,b+n*c
    if b==n:l.append(y)
    edge[a].append((1,x))
    edge[b].append((1,y))
    ex,ey=edge[x].append,edge[y].append
    ex((0,a))
    ex((0,y))
    ey((0,b))
    ey((0,x))
    used[a]=used[b]=used[x]=used[y]=True
    d[a]=d[b]=d[x]=d[y]=inf
  for i in edge:
    edge[i]=tuple(edge[i])
  d[1]=0
  used[1]=False
  edgelist=[]
  for e in edge[1]:
    heappush(edgelist,e)
  while edgelist:
    minedge=heappop(edgelist)
    if not used[minedge[1]]:
      continue
    v=minedge[1]
    d[v]=minedge[0]
    used[v]=False
    for e in edge[v]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+d[v],e[1]))
  a=min([d[i]for i in set(l)]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()

### FIXED CODE ###

def main():
  from heapq import heappush,heappop,heapify
  inf=2**31-1
  n,m,*t=map(int,open(0).read().split())
  z=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    z.extend([a,b,a+n*c,b+n*c])
  z={i:v for v,i in enumerate(sorted(set(z)))}
  try:
    z[1]
  except:
    print(-1)
    exit()
  edge=[[]for _ in range(len(z))]
  d={}
  l=[]
  for a,b,c in zip(t[::3],t[1::3],t[2::3]):
    if b<a:a,b=b,a
    i,j,x,y=z[a],z[b],z[a+n*c],z[b+n*c]
    if b==n:
      l.append(y)
    edge[i].append((1,x))
    edge[j].append((1,y))
    edge[x].extend([(0,i),(0,y)])
    edge[y].extend([(0,j),(0,x)])
  used=[False]+[True]*~-len(z)
  d=[0]+[inf]*~-len(z)
  edgelist=edge[0]
  heapify(edgelist)
  while edgelist:
    m=heappop(edgelist)
    if not used[m[1]]:
      continue
    d[m[1]]=m[0]
    used[m[1]]=False
    for e in edge[m[1]]:
      if used[e[1]]:
        heappush(edgelist,(e[0]+m[0],e[1]))
  a=min([d[i]for i in l]or[inf])
  print([a,-1][a==inf])
if __name__=='__main__':
  main()
### BUGGY CODE ###

# import bisect
# from collections import Counter, deque
# import copy
# from fractions import gcd
# from functools import reduce
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline

def resolve():

    N=int(input())
    s = str(input())


    l=['%03d'%(p) for p in range(0,10**3)]
    ans=[]
    for i in l:
        for j in range(N):
            if s[j]==i[0]:
                for k in range(j+1,N):
                    if s[k]==i[1]:
                        for m in range(k+1,N):
                            if s[m]==i[2]:
                                ans.append(i)

    print(len(set(ans)))


resolve()

### FIXED CODE ###


def resolve():

    N=int(input())
    s = str(input())


    l=['%03d'%(p) for p in range(0,10**3)]
    ans=[]
    for i in l:
        if i[0] in s:
            s0=s.index(i[0])
            if i[1] in s[s0+1:]:
                s1=s[s0+1:].index(i[1])
                if i[2] in s[s0+1:][s1+1:]:
                    ans.append(i)



    print(len(set(ans)))


resolve()
### BUGGY CODE ###



n=int(input())

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

ans+=n%1

print(ans)



### FIXED CODE ###

n=int(input())
sumNum=n*(n-1)//2
 
#print(r)
print(sumNum)
### BUGGY CODE ###

s=list(input())
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        s[i]=-1
    else:
        s[i]=int(s[i])

dp=[[0]*13 for i in range(len(s)+1)]
s.reverse()
dp[0][0]=1
y=[]
x=1
for i in range(len(s)):
    if s[i]!=-1:
        z=s[i]*x

        for j in range(13):
            dp[i+1][(j+z)%13]+=dp[i][j]
    else:
        for j in range(10):
            y.append((x*j)%13)

        for k in range(13):
            for l in range(len(y)):
                dp[i+1][(k+y[l])%13]+=dp[i][k]
        y=[]
    x=(x*10)%13
        
print(dp[len(s)][5]%mod)
            
        
        


     

    


### FIXED CODE ###

s=list(input())
mod=10**9+7
for i in range(len(s)):
    if s[i]=='?':
        s[i]=-1
    else:
        s[i]=int(s[i])

dp=[[0]*13 for i in range(len(s)+1)]
s.reverse()
dp[0][0]=1
y=[]
x=1
for i in range(len(s)):
    if s[i]!=-1:
        z=s[i]*x

        for j in range(13):
            dp[i+1][(j+z)%13]+=dp[i][j]%mod
    else:
        for j in range(10):
            y.append(x*j)

        for k in range(13):
            for l in range(len(y)):
                dp[i+1][(k+y[l])%13]+=dp[i][k]%mod
        y=[]
    x=(x*10)%13
        
print(dp[len(s)][5]%mod)
### BUGGY CODE ###

n,k = map(int,input().split())
if k==1 or n%k==0:
    print(0)
    exit()
while n > abs(n-k):
    n = abs(n-k)
print(n)

### FIXED CODE ###

n,k = map(int,input().split())
if n%k==0:
    print(0)
else:
    ans_a = n%k
    ans_b = abs(ans_a-k)
    print(min(ans_a,ans_b))
### BUGGY CODE ###

def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(input())
    cur = []
    visited = dict()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                cur.append([i, j])
                visited[(i, j)] = 1
            else:
                visited[(i, j)] = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    count = 0
    while cur:
        temp = []
        for i, j in cur:
            for di, dj in mv:
                i1, j1 = i+di, j+dj
                if 0 <= i1 < H and 0 <= j1 < W and not visited[(i1, j1)]:
                    visited[(i1, j1)] = True
                    temp.append([i1, j1])
        if len(temp) > 0:
            count += 1
        cur = temp
    return count

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import collections
def main():
    H, W = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(input())
    cur = []
    visited = collections.defaultdict(dict)
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                cur.append([i, j])
                visited[i][j] = 1
            else:
                visited[i][j] = 0
    mv = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    count = 0
    while cur:
        temp = []
        for i, j in cur:
            for di, dj in mv:
                i1, j1 = i+di, j+dj
                if 0 <= i1 < H and 0 <= j1 < W and not visited[i1][j1]:
                    visited[i1][j1] = True
                    temp.append([i1, j1])
        if len(temp) > 0:
            count += 1
        cur = temp
    return count

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

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

count = 0 # p_j > p_i である回数
for i in range(len(p_list)):
    flag = False
    for j in  p_list[:i+1]:
        if p_list[i]<=j:
            flag = True
        else:
          flag = False
          break
    if flag:
        count = count + 1

print(count)


### FIXED CODE ###

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

count = 0 # p_j > p_i である回数
p_length = len(p_list)
p_min = p_list[0] # 現時点での最小値

for i in range(p_length):
    if p_list[i]<=p_min:
        p_min = p_list[i]
        count = count + 1 # カウントを１つ増やす
    else:
        continue

print(count)
### BUGGY CODE ###

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


for _ in range(Q):
  b,c=map(int,input().split())
  time = A.count(b)
  if(time != 0):
    place = A.index(b)
    for i in range(time):
      A[place + i] = c
    A.sort()
  print(sum(A))

### FIXED CODE ###

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

num = [0]*(10**5+1)

sum = sum(A)
for i in range(N):
  num[A[i]-1] += 1

for _ in range(Q):
  b,c=map(int,input().split())
  sum += (c-b)*num[b-1]
  num[c-1] += num[b-1]
  num[b-1] = 0
  
  print(sum)
### BUGGY CODE ###

n,p=map(int,input().split())
ans=[]
if n==1:
  print(p)
else:
  for i in range(int(p**(1/n))+1):
    if p%(i+1)**n==0:
      ans.append((i+1))
  print(max(ans))


### FIXED CODE ###

n,p=map(int,input().split())
ans=[]
if n==1:
  print(p)
elif n>=40:
  print(1)
else:
  for i in range(int(p**(1/n))+1):
    if p%(i+1)**n==0:
      ans.append((i+1))
  print(max(ans))
### BUGGY CODE ###

import numpy as np

k = int(input())
r = np.zeros(k)

out = 1
s = 7 % k
while s != 0:
    n = s + 7 * (10 ** out)
    s = n % k
    if r[s] == 1:
        out = -1
        break
    if s != 0:
        r[s] = 1
    out += 1
print(out)

### FIXED CODE ###

k = int(input())
if k % 7 == 0:
    L = 9 * k // 7
else:
    L = 9 * k
out = -1
s = 10
for i in range(L):
    if s % L == 1:
        out = i + 1
        break
    else:
        s = (s % L) * 10
print(out)
### BUGGY CODE ###

from math import floor
A,B,N=list(map(int,input().split()))
ans = 0
for x in range(N,0,-1):
  a = floor(A*x/B)-A*floor(x/B)
  if ans <= a:
    ans = a
print(ans)

### FIXED CODE ###

from math import floor
A,B,N=list(map(int,input().split()))
x=min((B-1),N)
ans=floor(A*x/B)-A*floor(x/B)
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())

for i in o:
    """#weighted->erase_,__,___=map(int,input().split())
    edges[_].append((__,___))
    #undirected->erase#edges[__].append((_,___))
    """
    _,__=map(int,i.split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

    #undirected->erase#edges[__].append(_)
    """
"""#weighted->erase

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=set()
seen.add(3*s)
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if t not in seen:
            dq.append((t,c+1))
            seen.add(now)

print("-1")


### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
edges=[[] for i in range(3+3*n)]
o=inputs()
s,T=map(int,o.pop().split())
for i in o:
    _,__=map(int,i.split())
    _*=3;__*=3
    edges[_].append(__+1)
    edges[_+1].append(__+2)
    edges[_+2].append(__)

from collections import deque
dq=deque([])
dq.append((3*s,0))
T*=3
seen=[0]*(3*n+3)
seen[3*s]=1
while dq:
    now,c=dq.popleft()
    if now==T :print(c//3);exit()
    for t in edges[now]:
        if seen[t]==0:
            dq.append((t,c+1))
            seen[t]=1
print("-1")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
# 整数の入力
n = int(input())
# 文字列の入力
s = input()
# 数え上げ
count = 0
# for i in range(n):
#     for j in range(i+1, n):
#         for k in range(j+1, n):
#             if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
#                 count +=1
for i in range(n):
    for j in range(i+1, n):
        if s[i] != s[j]:
            for k in range(j+1, n):
                if s[j] != s[k] and s[k] != s[i] and j-i != k-j:
                    count +=1
print(count)

### FIXED CODE ###

n = int(input())
s = input()
count = s.count("R")*s.count("G")*s.count("B")
for i in range(n-2):
    for j in range(i+1, (i+n+1)//2):
        if s[j] != s[i] and s[j] != s[2*j-i] and s[i] != s[2*j-i]:
            count -= 1
        # print(i, j, 2*j-i, count)
print(count)
### BUGGY CODE ###

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

mod = 1000000000 + 7
ans = 0

for i in range(n):
    for j in range(n):
        pdt = 0
        if i<j:
            pdt = a[i] * a[j]
        ans %= mod
        ans += pdt

ans %= mod
print(ans)

### FIXED CODE ###

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

mod = 1000000000 + 7
ans = 0

for i in range(n):
    sum_a -= a[i]
    pdt = a[i] * sum_a
    ans += pdt

ans %= mod
print(ans)
### BUGGY CODE ###

# coding: utf-8

line = input()
data = line.split(" ")
shoplist = []
for i in range(int(data[0])):
    shop = input()
    shopdata = shop.split(" ")
    shop_int = []
    for j in range(len(shopdata)):
        shop_int.append(int(shopdata[j]))
    shoplist.append(shop_int)
shoplist.sort()
payment = 0
wantdrink = int(data[1])
while wantdrink > 0 :
    restdrink = shoplist[0][1]
    if restdrink >= wantdrink:
        payment += wantdrink * shoplist[0][0]
        break
    else:
        payment += restdrink * shoplist[0][0]
        wantdrink -= restdrink
        del shoplist[0]
print(payment)

### FIXED CODE ###

# coding: utf-8

data = input().split()
shoplist = []
for i in range(int(data[0])):
    shopdata = list(map(int, input().split()))
    shoplist.append(shopdata)
shoplist.sort()

payment = 0
wantdrink = int(data[1])
while wantdrink > 0 :
    restdrink = shoplist[0][1]
    if restdrink >= wantdrink:
        payment += wantdrink * shoplist[0][0]
        break
    else:
        payment += restdrink * shoplist[0][0]
        wantdrink -= restdrink
        del shoplist[0]
print(payment)
### BUGGY CODE ###

import math
N, K = list(map(int, input().split()))
A = list(map(int, input().split())) #A[0]〜A[N-1]

m = min(A)
answer = N

for i in range(N-K+1): #A[i:i+K]〜A[N-K:N]
  if min(A[i:i+K]) != m:
    continue
  answer = min(answer,
              (1 + math.ceil(i/(K-1)) + math.ceil((N-K-i)/(K-1))))
print(answer)

### FIXED CODE ###

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

print((N-1)//(K-1) + bool((N-1)%(K-1)))
### BUGGY CODE ###

import bisect
N = int(input())
numofcolor = 1
A = [0] * N
for i in range(N):
    A[i] = int(input())
listofmax = [A[0]]
for j in range(1, N):
    if listofmax[0] >= A[j]:
        numofcolor += 1
        listofmax.insert(0, A[j])
    else:
        listofmax[bisect.bisect_left(listofmax, A[j]) - 1] = A[j]
print(numofcolor)


### FIXED CODE ###

import bisect
from collections import deque
de1 = deque()
N = int(input())
A = [0] * N
for i in range(N):
    A[i] = int(input())
de1.appendleft(A[0])
for j in range(1, N):
    if de1[0] >= A[j]:
        de1.appendleft(A[j])
    else:
        de1[bisect.bisect_left(de1, A[j]) - 1] = A[j]
print(len(de1))