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

def main():
    import sys
    sys.setrecursionlimit(10**8)
    input=sys.stdin.readline
    n=int(input())
    a=list(map(int,input().split()))
    num1,num2,num3=0,0,0
    for i in range(n):
        if a[i]==1:
            num1+=1
        elif a[i]==2:
            num2+=1
        else:
            num3+=1
    dp=[[[-1 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
    def f(n1,n2,n3):
        if dp[n1][n2][n3]>=0:
            return dp[n1][n2][n3]
        if n1==n2==n3==0:
            return 0
        ret=0
        if n1>0:
            ret+=f(n1-1,n2,n3)*n1
        if n2>0:
            ret+=f(n1+1,n2-1,n3)*n2
        if n3>0:
            ret+=f(n1,n2+1,n3-1)*n3
        ret+=n
        ret*=1/(n1+n2+n3)
        dp[n1][n2][n3]=ret
        return dp[n1][n2][n3]
    print(f(num1,num2,num3))
if __name__=="__main__":
    main()

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

N = int(input())
A = list(map(int, input().split()))
dp = [[[0] * 301 for _ in range(301)] for _ in range(301)]

def rec(x, y, z):
    if dp[x][y][z] != 0:
        return dp[x][y][z]
    if x + y + z == 0:
        return 0
    res = N
    if x > 0:
        res += x * rec(x-1, y, z)
    if y > 0:
        res += y * rec(x+1, y-1, z)
    if z > 0:
        res += z * rec(x, y+1, z-1)
    dp[x][y][z] = res / (x + y + z)
    return dp[x][y][z]

M = [0] * 4
for a in A:
    M[a] += 1
ans = rec(M[1], M[2], M[3])
print("{:.10f}".format(ans))

### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
C = [0, A.count(1), A.count(2), A.count(3)]
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(C[3]+1):
    for j in range(C[3]+C[2]+1-k):
        for i in range(N+1-j-k):
            if i + j + k == 0:
                continue
            res = N
            if i > 0:
                res += i * dp[i-1][j][k]
            if j > 0:
                res += j * dp[i+1][j-1][k]
            if k > 0:
                res += k * dp[i][j+1][k-1]
            dp[i][j][k] = res / (i + j + k)
 
print(dp[C[1]][C[2]][C[3]])
### BUGGY CODE ###

n=int(input())
string_list=[input() for i in range(n)]
s=set(string_list)
t=list(s)
l=[0]*len(t)

for i in range(n):
  for j in range(len(t)):
    if t[j] == string_list[i]:
      l[j]+=1
u=[]
for k in range(len(t)):
  if l[k] == max(l):
    u.append(t[k])
u.sort()
for x in u:
	print(x)
      
      

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]

import collections
cnt = collections.Counter(s)
dict = sorted(cnt)

max_vote = max(cnt.values())
ans = []
for a,b in cnt.items():
  if max_vote == b:
    ans.append(a)
ans = sorted(ans)
print('\n'.join(ans))
### BUGGY CODE ###

# coding: utf-8
# N : 県の数, M: 市の数

N, M = map(int, input().split())
ps, ys = [], []

v = [ [] for _ in range(N+1) ]

for i in range(M):
    p, y = map(int, input().split())
    ps += [p]; ys += [y];
    v[p].append(y)

for i in range(N):
    v[i+1].sort()

for i in range(M):
    print("{:06d}".format(ps[i]), end="")
    print("{:06d}".format(v[ps[i]].index(ys[i])+1))


### FIXED CODE ###

# coding: utf-8
# N : 県の数, M: 市の数
import bisect

N, M = map(int, input().split())
ps, ys = [], []

v = [ [] for _ in range(N+1) ]

for i in range(M):
    p, y = map(int, input().split())
    ps += [p]; ys += [y];
    v[p].append(y)

for i in range(N):
    v[i+1].sort()


for i in range(M):
    print("{:06d}".format(ps[i]), end="")
    print("{:06d}".format(bisect.bisect_left(v[ps[i]], ys[i])+1))
### BUGGY CODE ###

n, k = map(int, input().split(' '))
w_s = [int(input()) for i in range(n)]

max_w = max(w_s)

while True:
    tmp_total_w = 0
    tmp_k = 1
    for w in w_s:
        tmp_total_w += w
        if tmp_total_w > max_w:
            tmp_k += 1
            tmp_total_w = w

    if tmp_k <= k:
        break

    max_w += 1

print(max_w)


### FIXED CODE ###

def calc_k_constP(P):
    tmp_total_w = 0
    tmp_k = 1
    for w in w_s:
        tmp_total_w += w
        if tmp_total_w > P:
            tmp_k += 1
            tmp_total_w = w

    return tmp_k

n, k = map(int, input().split(' '))
w_s = [int(input()) for i in range(n)]

max_w = max(w_s)

left, right = max_w, 10000 * n
while left < right:
    mid = (right + left) // 2
    tmp_k = calc_k_constP(mid)
    if tmp_k <= k:
        right = mid
    else:
        left = mid + 1

print(left)
### BUGGY CODE ###

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

m = 0
for i in range(n-k+1):
  m = max(m, sum(p[i:i+k]))
print((m + k)/2)

### FIXED CODE ###

import itertools

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

pa = list(itertools.accumulate([0] + p))

m = 0
for i in range(n-k+1):
  s = pa[i+k] - pa[i]
  if s > m:
    m = s
print((m+k)/2)
### BUGGY CODE ###

import copy

inf = 10 ** 9
n, m, R = [int(i) for i in input().split()]
r = [int(i) - 1 for i in input().split()]
dis = [[inf for _ in range(n)] for _ in range(n)]
for i in range(m):
    a, b, c = [int(i) for i in input().split()]
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

# 全ての頂点間の最短距離を算出、
for k in range(len(dis)):
    for i in range(len(dis)):
        for j in range(len(dis)):
            if dis[i][j] > dis[i][k] + dis[k][j]:
                dis[i][j] = dis[i][k] + dis[k][j]

def depth(visited, prev, last):
    if last == 0:
        # print("visited:{} prev:{}, last:{}".format(
            # visited, r[prev], last))
        return 0
    add = inf
    for i in range(len(visited)):
        if not visited[i]:
            _visited = copy.deepcopy(visited)
            _visited[i] = True
            add = min(add, dis[r[prev]][r[i]] + depth(_visited, i, last - 1))
            # print("add:{}".format(add))
    return add

_min = inf
for i in range(len(r)):
    # iをスタートとする
    visited = [False for _ in range(len(r))]
    visited[i] = True
    _min = min(_min, depth(visited, i, len(r) - 1))
print(_min)

"""
print("2 vs "+func(3, 3, [0, 1, 2], [[0, 1, 4], [1, 0, 1], [4, 1, 0]]))
print("4 vs "+func(3, 3, [0, 2], [[0, 2, 6], [2, 0, 2], [6, 2, 0]]))
print("3 vs "+func(4, 6, [1, 2, 3], [[0, 4, 6, 1], [4, 0, 3, 2], [6, 3, 0, 1], [1, 2, 1, 0]]))
# print("print(func({}, {}, {}, {}))".format(n, m, r, adj))
"""


### FIXED CODE ###

import itertools
n, m, R = map(int, input().split())
r = list(map(int, input().split()))
dis = [[float("inf") for _ in range(n)] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    dis[a - 1][b - 1] = c
    dis[b - 1][a - 1] = c

def war(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dis[i][j] > dis[i][k] + dis[k][j]:
                    dis[i][j] = dis[i][k] + dis[k][j]
    return dis
dis = war(dis)
_min = float("inf")
it = itertools.permutations(r)
for iterR in it:
    _dis = 0
    start = iterR[0] - 1
    for end in iterR[1:]:
        _dis += dis[start][end - 1]
        start = end - 1
    _min = min(_min, _dis)
print(_min)
### BUGGY CODE ###

def main():
  from sys import exit
  n = int(input())
  a = [list(map(int, input().split())) for _ in range(n)]
  ilist = [0] * n
  days = 1
  while True:
    booked = [False] * n
    books = 0
    for i in range(n):
      if booked[i]:
        continue
      ii = ilist[i]
      if ii == n - 1:
        continue
      j = a[i][ii] - 1
      if booked[j]:
        continue
      if a[j][ilist[j]] - 1 != i:
        continue
      books += 1
      booked[i] = True
      booked[j] = True
      ilist[i] += 1
      ilist[j] += 1
    if books == 0:
      print(-1)
      exit()
    if all(i == n - 1 for i in ilist):
      break
    days += 1
  print(days)
main()


### FIXED CODE ###

from sys import exit, setrecursionlimit
setrecursionlimit(1000000)

def dfs(v, dp, to):
  t = dp[v]
  if t >= 0:
    return t
  dp[v] = 0
  t = 0
  for u in to[v]:
    res = dfs(u, dp, to)
    if res == 0:
      print('-1')
      exit()
    if res > t:
      t = res
  t += 1
  dp[v] = t
  return t

def toId(i, j, id_db):
  if i < j:
    return id_db[i][j]
  else:
    return id_db[j][i]

def main():
  N = int(input())
  a = [[int(e) - 1 for e in input().split()] for _ in range(N)]

  id_db = [[0] * N for _ in range(N)]

  dp = [-1] * (N * (N - 1) // 2)
  to = [[] for _ in range(N * (N - 1) // 2)]

  v = 0
  for i in range(N):
    for j in range(i + 1, N):
      id_db[i][j] = v
      v += 1

  for i in range(N):
    for j in range(N - 1):
      a[i][j] = toId(i, a[i][j], id_db)
    for j in range(N - 2):
      to[a[i][j + 1]].append(a[i][j])

  print(max(dfs(i, dp, to) for i in range(N * (N - 1) // 2)))

main()
### BUGGY CODE ###

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

cd = a[0]

while a[0]%cd != 0 or a[1]%cd != 0:
    cd -= 1

print(cd)

### FIXED CODE ###

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

while a[0] > 0:
    b = a[1]%a[0]
    a[1] = a[0]
    a[0] = b
    
print(a[1])
### BUGGY CODE ###

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

#Aiは、Ai以外の任意の(すべての)Ajで割り切れない
unans = 0
for i in a:
  count = 0
  for j in a:
    if i % j == 0:
      count += 1
    if count >= 2:
      unans += 1
      break
   
print(n - unans)

### FIXED CODE ###

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

m = max(a)
#約分できちゃう数値リスト
lis = [0]*(m + 1)
for i in a:
  for j in range(i, m + 1, i):
    lis[j] += 1
#iが1なら、lisの要素全てに+1されてる。
count = 0
for i in a:
  if lis[i] == 1:
    count += 1
    
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

n = int(input())
H = list(map(int,input().split()))
dp = [0]*n

def rec(i):
    res = 0
    if i == 1 or i == 2:
        res = abs(H[i]-H[0])
        dp[i] = res
        return res
    elif i == 0:
        return 0
    if dp[i] != 0:
        return dp[i]
    else:
        res = min(abs(H[i]-H[i-2])+rec(i-2),abs(H[i]-H[i-1])+rec(i-1))
        dp[i] = res
    return res

rec(n-1)

print(dp[n-1]) 

### FIXED CODE ###

n = int(input())
H = list(map(int,input().split()))
dp = [0]*n

for i in range(1,n):
    if i == 1 or i == 2:
        dp[i] = abs(H[i]-H[0])
    else:
        dp[i] = min(abs(H[i]-H[i-2])+dp[i-2],abs(H[i]-H[i-1])+dp[i-1])

print(dp[n-1])
### BUGGY CODE ###

N, K = map(int, input().split())
H = tuple(map(int, input().split()))

if K >= N:
    print(abs(H[0] - H[N-1]))
else:
    dp = [abs(H[0] - H[i]) for i in range(K)] + [10**9] * (N - K)

    for i in range(K, N):
        for j in range(1, K+1):
            dp[i]= min(dp[i], dp[i-j] + abs(H[i] - H[i-j]))

    print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = tuple(map(int, input().split()))

if K >= N:
    print(abs(H[0] - H[N-1]))
else:
    dp = [abs(H[0] - H[i]) for i in range(K)] + [10**9] * (N - K)

    for i in range(K, N):
        for j in range(1, K+1):
            dp[i]= min(dp[i], dp[i-j] + abs(H[i] - H[i-j]))

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

from collections import deque
class G:
    def __init__(self, c):
        self.c = c
        self.reached = False
        self.range = 0

    
H, W = [int(i) for i in input().split()]
Ch, Cw = [int(i)-1 for i in input().split()]
Dh, Dw = [int(i)-1 for i in input().split()]
S = [['.' for j in range(W)] for i in range(H) ]
for i in range(H):
    tmp = list(input())
    for j in range(W):
        S[i][j] = G(tmp[j])

def neighbors(y, x):
    s = []
    if x != 0:
        if S[y][x-1].reached == False:
            s.append((y, x-1))
    if x != W-1:
        if S[y][x+1].reached == False:
            s.append((y, x+1))
    if y != 0:
        if S[y-1][x].reached == False:
            s.append((y-1, x))
    if y != H-1:
        if S[y+1][x].reached == False:
            s.append((y+1, x))
    return s

def jump(x, y, d):
    for i in range(max(x-2, 0), min(x+3, W)):
        for j in range(max(y-2, 0), min(y+3, H)):
            if S[j][i].reached == False and S[j][i].c == '.':
                d.append((j, i))



def DFS(S, d):
    while True:
        if len(d) == 0:
            break
        q = d.popleft()
        S[q[0]][q[1]].reached = True
        for each in neighbors(q[0], q[1]):
            S[each[0]][each[1]].reached = True
            if S[each[0]][each[1]].c == '.':
                d.append(each)


counter = 0
d = deque([])
S[Ch][Cw].reached = True
d.append((Ch, Cw))
flag = False
while True:
    DFS(S, d)
    if S[Dh][Dw].reached:
        break
    counter += 1
    for i in range(H):
        for j in range(W):
            if S[i][j].reached and S[i][j].c == '.':
                jump(j, i, d)

    if len(d) == 0:
        flag = True
        break

if flag:
    print(-1)
else:
    print(counter)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
import itertools
 
def main():
    input = sys.stdin.readline
    h, w = map(int, input().split())
    ch, cw = map(lambda x:int(x) - 1, input().split())
    dh, dw = map(lambda x:int(x) - 1, input().split())
    s = [list(input().rstrip()) for _ in range(h)]
    
    que = collections.deque()
    que.append((ch, cw))
    cost = [[float("INF")] * w for _ in range(h)]
    cost[ch][cw] = 0
    
    while que:
        py, px = que.popleft()
        for dy, dx in itertools.product(range(-2, 3), repeat = 2):
            ny, nx = py + dy, px + dx
            if 0 <= ny < h and 0 <= nx < w and s[ny][nx] == ".":
                if dy == dx == 0:
                    continue
                if (dy, dx) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                    if cost[ny][nx] > cost[py][px]:
                        cost[ny][nx] = cost[py][px]
                        que.appendleft((ny, nx))
                else:
                    if cost[ny][nx] > cost[py][px] + 1:
                        cost[ny][nx] = cost[py][px] + 1
                        que.append((ny, nx))
                        
    if cost[dh][dw] == float("INF"):
        print(-1)
    else:
        print(cost[dh][dw])
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

S = list(input())
N = len(S)

l = [0] * 2019
index = 0
temp = 0
for i in range(N-1, -1, -1):
    temp += int(S[i]) * pow(10,index) % 2019
    temp %= 2019
    l[temp] += 1
    index += 1

ans = l[0]

for i in range(1, 2019):
    ans += l[i] * (l[i]-1) // 2

print(ans)

### FIXED CODE ###

S = list(input())
N = len(S)

l = [0] * 2019
temp = 0
e = 1
for i in range(N-1, -1, -1):
    temp += int(S[i]) * e
    temp %= 2019
    l[temp] += 1
    e *= 10
    e %= 2019

ans = l[0]

for i in range(0, 2019):
    ans += l[i] * (l[i]-1) // 2

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

n=int(input())
a_list=list(map(int,input().split()))
ans=a_list[0]
for i in range(1,n):
    ans*=a_list[i]
if ans>10**18:
    ans=-1
        
print(ans)
        

### FIXED CODE ###

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

ans=a_list[0]
if 0 in a_list:
    ans=0
else:
    for i in range(1,n):
        ans*=a_list[i]
        if ans>10**18:
            ans=-1
            break
        
print(ans)
### BUGGY CODE ###

from collections import defaultdict


n, m = map(int, input().split())
m_dict = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    m_dict[a] = m_dict[a] + [b]
    

    
job_que = []
total = 0
for j in range(1, m+1):
    job_que.extend(m_dict[j])
 
 
    if job_que:
        job_que.sort()
        total += job_que.pop()
        
    
            
print(total)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
t_r_list = []
for i in range(n):
    t_r_list.append(list(map(int, input().split())))

t_r_list.sort()
que = []
total = 0
l = 0
for j in range(1, m + 1):
    while True:
        if l == n:
            break
        if t_r_list[l][0] != j:
            break
        heapq.heappush(que, -t_r_list[l][1])
        l += 1

    if que:
        total -= heapq.heappop(que)


print(total)
### BUGGY CODE ###

N,W = map(int, input().split())
w,v = [0]*N, [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())
    
# dp table
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j-w[i]<0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j],
                             dp[i][j-w[i]] + v[i])
print(dp[N][W])

### FIXED CODE ###

N,W = map(int, input().split())
w,v = [0]*N, [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())
    
dp = [0]*(W+1) 
for i in range(N):
    for j in reversed(range(W+1)):
        if j-w[i]<0:
            dp[j] = dp[j]
        else:
            dp[j] = max(dp[j],
                        dp[j-w[i]] + v[i])
    # print(dp)
print(dp[W])
### BUGGY CODE ###

n = int(input())
z = list(map(int,input().split()))
_sum = 0
y = len(z)
for i in range(y-1):
    a = z[i]
    b = sum(z[i+1:y])
    
    #print("b:"+str(b))
    _sum += (a*b)
        #print("_sum:"+str(_sum))
print(_sum % (10**9+7))

### FIXED CODE ###

n = int(input())
t = 10**9+7
z = list(map(int,input().split() ))
_sum = 0
x = sum(z)
y = len(z)
for i in range(y-1):
    x = x-z[i]
    _sum += (z[i]*x)
        #print("_sum:"+str(_sum))
print(_sum%t)
### BUGGY CODE ###

n = int(input())
s = list(int(input()) for i in range(n))

ans = 0
for bit in range(2 ** n):
    tmp = 0
    for i in range(n):
        if (bit >> i) & 1:
            tmp += s[i]
    
    if tmp % 10 != 0 and tmp > ans:
        ans = tmp

print(ans)


### FIXED CODE ###

n = int(input())
s = list(int(input()) for i in range(n))

s.sort()

ans = sum(s)

if ans % 10 != 0:
    print(ans)
    exit()
else:
    for x in s:
        if x % 10 != 0:
            ans -= x
            print(ans)
            exit()
print(0)
### BUGGY CODE ###

import numpy as np
N,M,Q = map(int,input().split())
LR = []
matrix = np.zeros((N,N)).astype('int')
for i in range(M):
    l,r = map(int,input().split())
    matrix[l-1][r-1] += 1
cumsums = []
for i in range(N):
    c = [0]
    for e in matrix[i]:
        c.append(c[-1]+e)
    cumsums.append(c)
for i in range(Q):
    p,q = map(int,input().split())
    p,q = p-1,q-1
    ans = 0
    for j in range(p,q+1):
        ans += cumsums[j][q+1]-cumsums[j][p]
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,M,Q = map(int,input().split())
LR = []
matrix = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    matrix[l][r] += 1
for i in range(N+1):
    for j in range(N):
        matrix[i][j+1] += matrix[i][j]
for i in range(N+1):
    for j in range(N):
        matrix[j+1][i] += matrix[j][i]
for i in range(Q):
    p,q = map(int,input().split())
    ans = matrix[q][q]-matrix[q][p-1]-matrix[p-1][q]+matrix[p-1][p-1]
    print(ans)
### BUGGY CODE ###

def list_1d(d,v):
    return [ v for i in range(d)]

h,w,d = [int(i) for i in input().split()]
sa = list_1d(h*w+1,[])
for i in range(h):
    a = [int(k) for k in input().split()]
    for j in range(w):
        sa[a[j]] = [i,j]
q = int(input())
lr = [[int(i) for i in input().split()] for i in range(q)]

def abs(c): 
    if c > 0: 
        return c 
    else: 
        return -c
    
def distance_2d(a,b):
    return(abs(a[0]-b[0])+abs(a[1]-b[1]))
    


for i in range(0,q):
    power = 0
    for j in range(lr[i][0],lr[i][1]-d+1,d):
        power += distance_2d(sa[j],sa[j+d])
    print(power)

### FIXED CODE ###

def list_1d(d,v):
    return [ v for i in range(d)]

def abs(c): 
    if c > 0: 
        return c 
    else: 
        return -c

def distance_2d(a,b):
    return(abs(a[0]-b[0])+abs(a[1]-b[1]))

h,w,d = [int(i) for i in input().split()]
sa = list_1d(h*w+1,[])
da = list_1d(h*w+1,0)
for i in range(h):
    a = [int(k) for k in input().split()]
    for j in range(w):
        sa[a[j]] = [i,j]
q = int(input())
lr = [[int(i) for i in input().split()] for i in range(q)]

for i in range(d+1,h*w+1):
    da[i] = da[i-d] + distance_2d(sa[i],sa[i-d])

for i in range(0,q):
    print(da[lr[i][1]]-da[lr[i][0]])
### BUGGY CODE ###

n = int(input())
s = list(input())
z = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        if s[i] != s[j]:
            for k in range(j+1, n):
                if s[i] != s[j] and s[j] != s[k] and s[i] != s[k] and k - j != j - i:
                    z += 1

print(z)

### FIXED CODE ###

n = int(input())
s = input()

nR = [0]*n
nG = [0]*n
nB = [0]*n
if s[-1] == 'R':
    nR[-1] = 1
elif s[-1] == 'G':
    nG[-1] = 1
elif s[-1] == 'B':
    nB[-1] = 1
for i in range(n-2, -1, -1):
    if s[i] == 'R':
        nR[i] = nR[i+1] + 1
        nG[i] = nG[i+1]
        nB[i] = nB[i+1]
    elif s[i] == 'G':
        nR[i] = nR[i+1]
        nG[i] = nG[i+1] + 1
        nB[i] = nB[i+1]
    elif s[i] == 'B':
        nR[i] = nR[i+1]
        nG[i] = nG[i+1]
        nB[i] = nB[i+1] + 1

cnt = 0
for i in range(n):
    for j in range(i, n-1):
        if s[i] != s[j]:
            f = 0
            if 2*j - i < n:
                if s[i] != s[2*j-i] and s[j] != s[2*j-i]:
                    f = 1

            if s[i] != 'R' and s[j] != 'R':
                cnt += nR[j] - f
            elif s[i] != 'G' and s[j] != 'G':
                cnt += nG[j] - f
            elif s[i] != 'B' and s[j] != 'B':
                cnt += nB[j] - f

print(cnt)
### BUGGY CODE ###

s = input()
s = [si for si in s]
ans = 0
 
while True:
  st = ans
  for i in range(len(s) - 1):
    if s[i] == 'B' and s[i+1] == 'W':
      s[i] = 'W'
      s[i+1] = 'B'
      ans += 1
  if st == ans:
    print(ans)
    break

### FIXED CODE ###

s = input()
w = 0
b = 0
wa = 0
ba = 0
l = len(s)
 
for i in range(l):
  if s[i] == 'W':
    wa += i - w
    w += 1
  if s[-1-i] == 'B':
    ba += i - b
    b += 1
    
print(min(ba, wa))
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
n = int(input())
v = np.array([(0,0,0)]+[tuple(map(int, input().split( ))) for i in range(n)])


for i in range(n):
    if (v[i+1]+v[i]).sum()%2:
        print("No")
        exit()
    if v[i+1][0]-v[i][0]<abs(v[i+1][1:]-v[i][1:]).sum():
        print("No")
        exit()
print("Yes")


### FIXED CODE ###


n = int(input())
v = [(0,0,0)]+[tuple(map(int, input().split( ))) for i in range(n)]


for i in range(n):
    if (v[i+1][0]+v[i][0]+v[i+1][1]+v[i][1]+v[i+1][2]+v[i][2])%2:
        print("No")
        exit()
    if v[i+1][0]+v[i][0]<abs(v[i+1][1]-v[i][1])+abs(v[i+1][2]-v[i][2]):
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

import collections
import math
N = int(input())
A = list(map(int, input().split()))
ans = 0

for i in range(N):
  li = A[:i] + A[i+1:]
  c = collections.Counter(li)
  l = [i[1] for i in c.items() if i[1] > 1]
  for num in l:
    ans += math.factorial(num) // (math.factorial(num-2) * 2)
  print(ans)
  ans = 0

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
total = 1

for n in c.items():
  total += n[1]*(n[1]-1)//2

for i in range(N):
  print(total-c[A[i]])
### BUGGY CODE ###

N = int(input())
S = input()
c = 0
for i in range(1000):
    s = "0"*(3-len(str(i)))+str(i)
    #print(s)
    k = 0
    for j in S:
        if j == s[k]:
            k += 1
            if k == 3:
                c += 1
                #print(s)
                break
        #print("j={},k={}".format(j,k))
print(c)

### FIXED CODE ###

N = int(input())
S = input()

y = 0
L = []
for i in range(10):
    for j in range(10):
        L = []
        # print(i,j,k)
        c = str(i)
        p = 0
        l = 0
        while l < N:
            if p == 0 and S[l] == c:
                c = str(j)
                p = 1
            elif p == 1 and S[l] == c:
                p = 2
            elif p == 2 and S[l] not in L:
                L.append(S[l])
            l += 1
        y += len(L)
print(y)