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

import collections

num = int(input())
s = sorted(list(map(int, input().split())))
if num == 1:
    print(1)
else:
    max_ans = 0
    for i in range(num):
        start = s[i]
        c = collections.Counter(s)
        current_ans = c[start]+c[start+1]+c[start+2]
        max_ans = max(current_ans,max_ans)
    print(max_ans) 

### FIXED CODE ###

import collections

num = int(input())
s = sorted(list(map(int, input().split())))
if num == 1:
    print(1)
else:
    c = collections.Counter(s)
    max_ans = 0
    for i in range(num):
        start = s[i]
        current_ans = c[start]+c[start+1]+c[start+2]
        max_ans = max(current_ans,max_ans)
        i += c[start]
    print(max_ans)
### BUGGY CODE ###

N=int(input())
L=input().split()
A=[int(a) for a in L]
B=sorted(A)
answer=0
for a in range(N-1):
    number=1
    while a+number<N-1:
        suuji = number + 1
        saisho=B[a]
        tonari=B[a+number]
        goukei=saisho+tonari
        while a+suuji<N:
            tar=B[a+suuji]
            if goukei>tar:
                answer+=1
            else:
                break
            suuji+=1
        number+=1
print(answer)


### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
sort_L=sorted(L,reverse=True)
ans=0
for n in range(N-2):
    for o in range(n+1,N-1):
        lar=sort_L[n]
        kouho=sort_L[o+1:]
        mid=sort_L[o]
        sa=lar-mid
        left=0
        right=N-o-2
        if kouho[-1]>sa:
            ans+=right+1
        else:
            while right > left + 1:
                half = (right + left) // 2
                if kouho[half] <= sa:
                    right = half
                else:
                    left = half
            if kouho[right]<=sa and kouho[left]<=sa:
                continue
            elif kouho[right]>sa:
                ans+=right+1
            else:
                ans+=left+1
print(ans)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
links = [list(map(int, input().split())) for _ in range(N-1)]

def perm(a, b):
    s = 1
    for i in range(a-b+1, a+1):
        s *= i
    return s

def main():
    if N == 1:
        return K
    d = {i: set() for i in range(1, N+1)}
    for i, j in links:
        d[i].add(j)
        d[j].add(i)
    history = {1}
    stack = d[1]
    b = len(stack)
    if K - 1 < b:
        return 0
    d.pop(1)
    ans = K * perm(K - 1, b)
    a = K - 2
    lim = max([len(x) for x in d.values()])
    if lim - 1 > a:
        return 0
    lim += 1
    perm_list = [None] * lim
    perm_list[0] = 1
    for i in range(1, lim):
        perm_list[i] = perm_list[i-1] * (a + 1 - i)
    while stack:
        node = stack.pop()
        if node in history:
            continue
        history.add(node)
        ans *= perm_list[len(d[node]) - 1]
        ans %= 1000000007
        stack |= d[node]
    return ans
    
print(main())


### FIXED CODE ###

N, K = list(map(int, input().split()))
l = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b = list(map(int, input().split()))
    l[a].append(b)
    l[b].append(a)

deg1 = [0] * (N + 1)
deg2 = [0] * (N + 1)
history = [True] * (N + 1)
stack = [1]
ans = 1

while stack:
    node = stack.pop()
    ans *= K - deg1[node] - deg2[node]
    ans %= 1000000007
    history[node] = False
    for child in l[node]:
        if history[child]:
            deg1[child] += 1
            deg2[child] += deg1[node]
            deg1[node] += 1
            stack.append(child)
            
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())
dp = [0 for i in range(W+1)]

for i in range(N):
  wi, vi = map(int, input().split())
  for w in range(W, wi-1, -1):
    dp[w] = max(dp[w], dp[w-wi]+vi)

print(max(dp))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))
 
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import math
n, h = map(int, input().split())
l = []
ans = 0

for tmp in range(n):
    a, b = map(int, input().split())
    l.append((a,b))

factor = sorted(l, key=lambda tmp:tmp[1])

while h > 0:
    max_a = max(l, key=lambda tmp:tmp[0])
    if len(factor) != 0:
        max_b = factor[-1]
    else:
        max_b = (-1,-1)
    if max_a[0] < max_b[1] and max_b != (-1,-1):
        h -= max_b[1]
        factor.pop()
        ans += 1
    else:
        ans += math.ceil(h/max_a[0])
        h -= max_a[0]*math.ceil(h/max_a[0])
print(ans)

### FIXED CODE ###

# -*- coding:utf-8 -*-
import math
n, h = map(int, input().split())
l = []
ans = 0

for tmp in range(n):
    a, b = map(int, input().split())
    l.append((a,b))

factor = sorted(l, key=lambda tmp:tmp[1])
max_a = max(l, key=lambda tmp:tmp[0])
while h > 0:
    if len(factor) != 0:
        max_b = factor[-1]
    else:
        max_b = (-1,-1)
    if max_a[0] < max_b[1]:
        h -= max_b[1]
        factor.pop()
        ans += 1
    else:
        ans += math.ceil(h/max_a[0])
        h -= max_a[0]*math.ceil(h/max_a[0])
print(ans)
### BUGGY CODE ###

import numpy as np
import math
N = int(input())
sum = 0;
for n in range(0,len(str(N))):
  sum = sum + (N % 10)
  N = N // 10
if sum % 9 == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

import numpy as np
import math
strN = input()
splN = list(strN)
intN = [int(s) for s in splN]
sumN = sum(intN)
if sumN % 9 == 0:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

from operator import mul
from functools import reduce
O = pow(10, 18)
N = int(input())
L = list(map(int, input().split()))
M = reduce(mul, L)
if O < M:
    M = -1
print(M)

### FIXED CODE ###

import sys
O = pow(10, 18)
N = int(input())
L = list(map(int, input().split()))
M = 1

if 0 in L:
    print(0)
    sys.exit()

for i in range(N):
    M = M * L[i]
    if O < M:
        print(-1)
        sys.exit()
    else:
        continue
print(M)
### BUGGY CODE ###

import heapq 
n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit()
lrd = [list(map(int, input().split())) for _ in range(m)]
heapq.heapify(lrd)
di = {i:'?' for i in range(n+1)}
di[lrd[0][0]] = 0
while lrd:
    l, r, d = heapq.heappop(lrd)
    if di[l] == '?' and di[r] == '?':
        heapq.heappush(lrd, [l, r, d])
    elif di[l] != '?' and di[r] == '?':
        di[r] = di[l] + d  
    elif di[l] == '?' and di[r] != '?':
        di[l] = di[r] - d 
    else:
        if di[l] + d != di[r]:
            print('No')
            exit()

print('Yes')

### FIXED CODE ###


import sys
sys.setrecursionlimit(10**5)
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
        self.weight = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            r = self.Find_Root(self.root[x])
            self.weight[x] += self.weight[self.root[x]]
            self.root[x] = r
            return r
    def GetWeight(self, x):
        self.Find_Root(x)
        return self.weight[x]
    def Unite(self, x, y, w):
        w += self.GetWeight(x)
        w -= self.GetWeight(y)
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return False
        if self.rnk[x] < self.rnk[y]:
            x, y = y, x
            w = -w
        if self.rnk[x] == self.rnk[y]:
            self.rnk[x] += 1
        self.root[y] = x
        self.weight[y] = w
        return True
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x):
        return -self.root[self.Find_Root(x)]
    def Diff(self, x, y):
        return self.GetWeight(y) - self.GetWeight(x)

n, m = map(int, input().split())
if m == 0:
    print('Yes')
    exit()
lrd = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n)
for l, r, d in lrd:
    if uf.isSameGroup(l, r)==False:
        uf.Unite(l, r, d)
    else:
        if uf.Diff(l, r) != d:
            print('No')
            exit()
print('Yes')
### BUGGY CODE ###

import numpy as np
import sys
import math
read = sys.stdin.readline

N = int(read().rstrip())
A = list(map(int,read().rstrip().split()))
da = []
for i , a in enumerate(A):
    da.append([i,a])

sumN = [0] * N
for i , a in enumerate(A):
    sumN[i] = i + a + 1

sumN = sorted(sumN)

newA = sorted(da , key = lambda x:(x[1]))
ans = 0

for s in sumN :
    if s > 200000:
        break

    for a in newA :
        if s + a[1] > 200000:
            break

        if s  + a[1]  == a[0] + 1:
            ans += 1

print(ans)


### FIXED CODE ###

import numpy as np
import sys
import math
read = sys.stdin.readline

N = int(read().rstrip())
A = list(map(int,read().rstrip().split()))
da = []
for i , a in enumerate(A):
    da.append([i,a])

dR = {}
dL = {}

ans = 0
for d in reversed(da):
    r = d[0] + d[1] + 1
    l = d[0] - d[1] + 1 
    if r in dR:
        dR[r] += 1
    else:
        dR[r] = 1

    if r in dL:
        ans += dL[r]

    if l in dL :
        dL[l] += 1
    else:
        dL[l] = 1  

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

import numpy as np


def main():
    N = int(input())
    A = np.array([])
    B = np.array([])
    for i in range(0, N):
        a, b = map(int, input().split())
        A = np.append(A, [a])
        B = np.append(B, [b])
    
    # 自分に一番良い手と相手にとって一番良い手を考える
    # 自分にとって一番良い手が複数ある場合、その中で相手が一番良い手を選ぶ
    # 自分にとって一番良い手が１つの場合、相手にとって一番良い手との比較をして、差が大きい方を選ぶ
    # 自分にとって良いてと相手にとっていい手が同じ場合(相手にとっていい手が複数ある場合も)、それを選ぶ
    takahashi = 0
    aoki = 0
    # 足し算して一番大きいところからとる
    sum_AB = A + B
    #  print(A, B)
    for i in range(1, N + 1):
        max_idx = np.argmax(sum_AB)
        #  print(sum_AB, max_idx)
        if i % 2 == 1:
            takahashi += A[max_idx]
        else:
            aoki += B[max_idx]
        sum_AB[max_idx] = -1

    print(int(takahashi - aoki))


def sub(N, A, B):
    takahashi = 0
    aoki = 0
    # 足し算して一番大きいところからとる
    sum_AB = A + B
    #  print(A, B)
    for i in range(1, N + 1):
        max_idx = np.argmax(sum_AB)
        #  print(sum_AB, max_idx)
        if i % 2 == 1:
            takahashi += A[max_idx]
        else:
            aoki += B[max_idx]
        sum_AB[max_idx] = -1

    print(int(takahashi - aoki))



main()


### FIXED CODE ###

import numpy as np


def main():
    N = int(input())
    A = []
    B = []
    for i in range(0, N):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
    
    takahashi = 0
    aoki = 0
    # 足し算して一番大きいところからとる
    A = np.array(A)
    B = np.array(B)
    sum_AB = A + B
    l = sum_AB.argsort()[::-1]
    takahashi = sum([A[i] for i in [j for idx, j in enumerate(l) if idx % 2 == 0]])
    aoki = sum([B[i] for i in [j for idx, j in enumerate(l) if idx % 2 != 0]])

    print(int(takahashi - aoki))


main()
### BUGGY CODE ###

import bisect

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

alphabet = [chr(ord('a') + i) for i in range(26)]

d = {alphabet[i]: [] for i in range(26)}
for i, a in enumerate(s):
    d[a].append(i)

ans = []
for i in range(q):
    query = input().split()

    if query[0] == '1':
        idx, c = int(query[1]) - 1, query[2]
        d[s[idx]].remove(idx)
        bisect.insort_left(d[c], idx)
        s[idx] = c
    else:
        l, r = int(query[1]) - 1, int(query[2]) - 1
        res = 0
        for c in alphabet:
            if bisect.bisect_right(d[c], r) > bisect.bisect_left(d[c], l):
                res += 1
        ans.append(res)

for i in ans:
    print(i)

### FIXED CODE ###

import bisect

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

alphabet = [chr(ord('a') + i) for i in range(26)]

d = {alphabet[i]: [] for i in range(26)}
for i, a in enumerate(s):
    d[a].append(i)

ans = []
for i in range(q):
    query = input().split()

    if query[0] == '1':
        idx, c = int(query[1]) - 1, query[2]
        if s[idx] == c:
            continue
        d[s[idx]].remove(idx)
        bisect.insort_left(d[c], idx)
        s[idx] = c
    else:
        l, r = int(query[1]) - 1, int(query[2]) - 1
        res = 0
        for c in alphabet:
            if bisect.bisect_right(d[c], r) > bisect.bisect_left(d[c], l):
                res += 1
        ans.append(res)

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

n = int(input())
a = list(map(int,input().split()))
for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
li = [0]*n
for i in a:
    li[i-1] += 1
print(*li, sep="\n")
### BUGGY CODE ###

D = 10 ** 9 + 7
N = int(input())
L= list(map(int, input().split()))

ans = L[0] * L[1] % D
for n in range(2,N):
  for l in range(n):
    ans += L[n] * L[l] % D

print(ans % D)


### FIXED CODE ###

D = 10 ** 9 + 7
N = int(input())
L= list(map(int, input().split()))

ans = L[0] * L[1] % D
sub = L[0] + L[1]
for n in range(2,N):
    ans += L[n] * sub
    sub += L[n]
    
print(ans % D)
### BUGGY CODE ###

a, b, x = map(int, input().split())
total1 = 0
for i in range (a, b+1):
    if i % x == 0:
        total1 += 1
print(total1)

### FIXED CODE ###

a, b, x = map(int, input().split())
print(b // x - (a - 1) // x)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    A_ = []
    indices = []
    tmp = sorted(enumerate(A), reverse=True, key=lambda x:x[1])
    for row in tmp:
        k, v = row
        indices.append(k)
        A_.append(v)
    A = A_
    
    dp = [[0 for i in range(N+1)] for j in range(N+1)]
    for i in range(N):
        for j in range(0, N-i):
            a = A[i+j]
            idx = indices[i+j]
            dp[i+1][j] = max(dp[i+1][j], dp[i][j] + a * abs(idx - i))
            dp[i][j+1] = max(dp[i][j+1], dp[i][j] + a * abs(N - 1 - j - idx))
    result = -1
    for i in range(N):
        tmp = dp[i][N-i]
        if tmp > result:
            result = tmp
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    A = sorted(enumerate(A), reverse=True, key=lambda x: x[1])

    dp = [[0 for i in range(N + 1)] for j in range(N + 1)]
    for i in range(N):
        for j in range(0, N - i):
            idx, a = A[i + j]
            #idx = indices[i + j]
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a * abs(idx - i))
            dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + a * abs(N - 1 - j - idx))
    result = -1
    for i in range(N):
        tmp = dp[i][N - i]
        if tmp > result:
            result = tmp
    print(result)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


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

#066-C
n=int(input())
a=list(map(int,input().split()))
b=[]
if n%2==0:
    for i in range(n):
        if i%2==0:
            b=b+[a[i]]
        else:
            b=[a[i]]+b
else:
     for i in range(n):
        if i%2==1:
            b=b+[a[i]]
        else:
            b=[a[i]]+b
for i in range(n):
    print(b[i],end=" ")
print()

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a1=[]
a2=[]
for i in range(n):
    if i%2==0:
        a1.append(a[i])
    else:
        a2.append(a[i])
if n%2==0:
    a2.reverse()
    b=a2+a1
else:
    a1.reverse()
    b=a1+a2
for i in range(n):
    print(b[i],end=" ")
print()
### BUGGY CODE ###

from sys import stdin
def main():
    readline = stdin.readline
    N = int(input())
    A = list(map(int, readline().split()))
    listN = list(range(1, N+1))    

    for i in listN:
        print(A.count(i))
main()


### FIXED CODE ###

from sys import stdin
import collections

def main():
    readline = stdin.readline
    N = int(input())
    A = list(map(int, readline().split()))
    listN = list(range(1, N+1))    
    c = collections.Counter(A)
    
    for i in listN:
        print(c[i])
main()
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
while len(a) > 0:
  lena = len(a)
  ban = a.pop(0)
  ans = ans + (ban * sum(a[0:lena]))
if ans > 10 **9:
  ans = ans % (10 **9 + 7)
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = 0
Sum = sum(a)
for i in range(n):
  Sum = Sum- a[i]
  ans = ans  + a[i] * Sum
if ans > 10 ** 9:
  ans = ans % (10 **9 + 7)
print(ans)
### BUGGY CODE ###

N = int(input())

A2N = list(map(int, input().split()))

for i in range(1, N):
    print(A2N.count(i))
print(0)

### FIXED CODE ###

N = int(input())

A2N = list(map(int, input().split()))
import collections
c = collections.Counter(A2N)
for i in range(1, N):
    if i in c.keys():
        print(c[i])
    else:
        print(0)
print(0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.num = [1] * (n + 1)

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            self.num[x] = self.num[self.parent[x]]
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        numx = self.num[x]
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        self.num[x] += self.num[y]
        self.num[y] += numx

    def same_check(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
inconv = n * (n - 1) // 2
inconv_list = []
inconv_list.append(inconv)

uf = UnionFind(n)
for i in range(m - 1, 0, -1):
    a, b = edge[i][0], edge[i][1]
    if not uf.same_check(a, b):
        inconv -= uf.num[a] * uf.num[b]
        uf.union(a, b)
    else:
        inconv = inconv
    inconv_list.insert(0, inconv)
print(*inconv_list, sep="\n")


### FIXED CODE ###

import sys
input = sys.stdin.readline

class UnionFind:
    def __init__(self, n):
        self.parent = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.num = [1] * (n + 1)

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            self.num[x] = self.num[self.parent[x]]
            return self.parent[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        numx = self.num[x]
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        self.num[x] += self.num[y]
        self.num[y] += numx

    def same_check(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
edge = [list(map(int, input().split())) for _ in range(m)]
inconv = n * (n - 1) // 2
inconv_list = [0] * m
inconv_list[m - 1] = inconv

uf = UnionFind(n)
for i in range(m - 1, 0, -1):
    if inconv == 0:
        break
    a, b = edge[i][0], edge[i][1]
    if not uf.same_check(a, b):
        inconv -= uf.num[a] * uf.num[b]
        uf.union(a, b)
    else:
        inconv = inconv
    inconv_list[i - 1] = inconv
print(*inconv_list, sep="\n")
### BUGGY CODE ###

N=int(input())
import sys
ab=[list(map(int, input().split())) for _ in range (N-1)]
con=[[] for _ in range(N+1)]

#print(ab)
for a,b in ab :
  con[a].append(b)
  con[b].append(a)

#black Fennec
pc=[0]*(N+1)
q=[(1,0)]
vis=[False]*(N+1)
vis[1]=True
Fcnt=N
while q:
  n,c=q.pop()
  pc[n]=c
  for ch in con[n]:
    if vis[ch]==True:
      continue
    q.append((ch,c+1))
    
q=[(N,0)]
vis=[False]*(N+1)
vis[1]=True
while q:
  n,c=q.pop()
  if pc[n]>c:
    Fcnt-=1
  for ch in con[n]:
    if vis[ch]==True:
      continue
    q.append((ch,c+1))
    
if Fcnt>N-Fcnt:
  print("Fennec")
else:
  print("Snuke")


### FIXED CODE ###

N=int(input())

import sys
sys.setrecursionlimit(10**5)
ab=[list(map(int, input().split())) for _ in range (N-1)]
con=[[] for _ in range(N+1)]

#print(ab)
for a,b in ab :
  con[a].append(b)
  con[b].append(a)

#black Fennec
pc=[0]*(N+1)
q=[(1,0)]
vis=[False]*(N+1)
vis[1]=True
Fcnt=N
while q:
  n,c=q.pop()
  pc[n]=c
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
q=[(N,0)]
vis=[False]*(N+1)
vis[N]=True
while q:
  n,c=q.pop()
  if pc[n]>c:
    Fcnt-=1
  for ch in con[n]:
    if vis[ch]==True:
      continue
    vis[ch]=True
    q.append((ch,c+1))
    
if Fcnt>N-Fcnt:
  print("Fennec")
else:
  print("Snuke")
### BUGGY CODE ###

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

ans=0
for j in range(1,n-1):
    for i in range(j):
        for k in range(j+1,n):
            if (j-i)!=(k-j) and s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
                ans+=1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r_count = s.count('R')
g_count = s.count('G')
b_count = s.count('B')

count=0
for i in range(n):
    a = s[i]
    for j in range(i+1,n):
        if (2*j-i)>(n-1):
            continue
        b=s[j]
        c=s[2*j-i]
        if a!=b and b!=c and a!=c:
            count+=1
print(r_count*g_count*b_count-count)
### BUGGY CODE ###

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

X = [a / 2 for a in A]
c = 0
for m in range(1, M + 1):
    if [m % a for a in A] == X:
        c += 1
print(c)

### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
A = [a//2 for a in A]

def lcm(a, b):
    return (a*b) // gcd(a, b)

k = A[0]
for a in A[1:]:
    k = lcm(a, k)

M = M - (M % k)
b = M // k


if b % 2 == 0:
    r = int(b/2)
else:
    r = int((b + 1) / 2)

for a in A[1:]:
    if k // a % 2 == 0:
        r = 0
        break

print(r)
### BUGGY CODE ###

S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
mod = 10**9 + 7
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1

    if s == "B" or s == "?":
        ans += ((ql * 3**max(0, ql-1) + a * 3**ql) % mod) * ((qr * 3**max(0, qr-1) + c * 3**qr) % mod)
        ans %= mod

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1

print(ans)


### FIXED CODE ###

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
mod = 10**9 + 7
ql3 = 1
qr3 = 1
for i in range(qr):
    qr3 *= 3
    qr3 %= mod
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1
        qr3 *= modinv(3, mod)
        qr3 %= mod

    if s == "B" or s == "?":
        ans += ((ql * ql3 * modinv(3, mod) + a * ql3) % mod) * ((qr * qr3 * modinv(3, mod) + c * qr3) % mod)
        ans %= mod

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1
        ql3 *= 3
        ql3 %= mod

print(ans)