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

N, K = [int(n) for n in input().split()]
P = [(int(n)+1)/2 for n in input().split()]
ans = sum(P[:K])
for i in range(1, N-K+1):
    e = sum(P[i:i+K])
    if ans < e:
        ans = e
print(ans)

### FIXED CODE ###

N, K = [int(n) for n in input().split()]
P = [(int(n)+1)/2 for n in input().split()]
ans = sum(P[:K])
e = ans
for p,x in zip(P, P[K:]):
    e = e-p+x
    if ans < e:
        ans = e
print(ans)
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())

X = []

i = 0
while i < N:
    X.append(list(map(int, input().split())))
    i += 1

X = np.asarray(X)

X_ind = np.argsort(X[:,0], axis=0)
X = X[X_ind]
# print(X)
least = 1
p = 0
while least <= M:
    # print(least)
    best_index = -1
    best_s = 0
    for i in range(X.shape[0]):
        target = X[i]
        if least >= target[0] and best_s <= target[1]:
            best_index = i
            best_s = target[1]
        elif least < target[0]:
            break
    # print(target)
    p += best_s
    if best_index >= 0:
        X = np.delete(X, best_index, axis=0)
    least += 1

print(p)


### FIXED CODE ###

from heapq import heappush,heappop
N, M = map(int, input().split())

X = []

for _ in range(N):
    a, b = map(int, input().split())
    if a <= M:
        X.append((a,b))


X = sorted(X, key=lambda x:(x[0], x[1]), reverse=True)

# print(X)
q = []
ans = 0
for i in range(1, M + 1):
    while X and X[-1][0] <= i:
        _, b = X.pop()
        heappush(q, -b)
    if q:
        ans -= heappop(q)
        
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr()
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 10 ** 2)):
    next = [0] * N
    for i in range(N):
        x = A[i]
        for j in range(max(0, i-x), min(N-1, i+x)+1):
            next[j] += 1
    A = next

print(*A)

### FIXED CODE ###

# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, K = lr()
A = lr() + [0]
# ある回数から先は全ての電球にNを足す
for _ in range(min(K, 41)):
    next = [0] * (N+1)
    for i in range(N):
        x = A[i]
        next[max(0, i-x)] += 1
        next[min(N-1, i+x)+1] -= 1
    for i in range(N):
        next[i+1] += next[i]
    A = next.copy()

print(*A[:-1])
### BUGGY CODE ###

N,M=map(int,input().split())
e=[int(x)-1 for x in input().split()]
p=[i for i in range(N)]
r=[0]*N

def find(x):
	if p[x]!=x:
		p[x]=find(p[x])
	return p[x]

def unite(x,y):
	x=find(x)
	y=find(y)
	if x==y:
		return

	if r[x]<r[y]:
		p[x]=y
	else:
		p[y]=x
		if r[x]==r[y]:
			r[x]+=1

def same(x,y):
	return find(x)==find(y)

for i in range(M):
	x,y=map(int,input().split())
	unite(x-1,y-1)

l=list()
for i in range(N):
	f=False	
	for j in l:
		if j[0]==find(i):
			j[1].add(i)
			f=True
			break
	if not f:
		l.append([find(i),set([i])])

c=0
for i in l:
	for j in i[1]:
		if e[j] in i[1]:
			c+=1

print(c)


### FIXED CODE ###

N,M=map(int,input().split())
e=[int(x)-1 for x in input().split()]
p=[i for i in range(N)]
r=[0]*N

def find(x):
	if p[x]!=x:
		p[x]=find(p[x])
	return p[x]

def unite(x,y):
	x=find(x)
	y=find(y)
	if x==y:
		return

	if r[x]<r[y]:
		p[x]=y
	else:
		p[y]=x
		if r[x]==r[y]:
			r[x]+=1

def same(x,y):
	return find(x)==find(y)

for i in range(M):
	x,y=map(int,input().split())
	unite(x-1,y-1)

c=0
for i in range(N):
	if same(i,e[i]):
		c+=1

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

from collections import deque
N,M=map(int,input().split())
G=[[] for i in range(N)]
for i in range(M):
  a,b=map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
Q=int(input())
Colors=[0]*N
dp=[[False]*11 for i in range(N)]
def BFS(v,d,c):
  global dp
  for i in range(d+1):
    dp[v][i]=True
  stack=deque([(v,d)])
  global Colors
  while stack:
    n,m=stack.popleft()
    if m<0:
      break
    if Colors[n]==0:
      Colors[n]=c
    for u in G[n]:
      if not dp[u][m]:
        stack.append((u,m-1))
        for i in range(m):
          dp[u][i]=True
q=[list(map(int,input().split())) for i in range(Q)]
for i in q[::-1]:
  v,d,c=i
  BFS(v-1,d,c)
for c in Colors:
  print(c)


### FIXED CODE ###

N,M=map(int,input().split())
E=[]
for i in range(M):
  a,b=map(int,input().split())
  E.append((a-1,b-1))
Q=int(input())
dp=[[-1]*11 for i in range(N)]
C=[]
for i in range(Q):
  v,d,c=map(int,input().split())
  dp[v-1][d]=i
  C.append(c)
for d in range(1,11)[::-1]:
  for n in range(N):
    dp[n][d-1]=max(dp[n][d],dp[n][d-1])
  for a,b in E:
    dp[a][d-1]=max(dp[a][d-1],dp[b][d])
    dp[b][d-1]=max(dp[b][d-1],dp[a][d])
for i in range(N):
  if dp[i][0]>=0:
    print(C[dp[i][0]])
  else:
    print(0)
### BUGGY CODE ###

s,t = input(),input()
x,r,nx,p = s*2,0,{},'.'

for i,c in enumerate(s):
	nx[('.',c)] = i+1
	for j in range(i+1,len(x)):
		if nx.get((c,x[j])) is None:
			nx[(c,x[j])] = j-i

for c in t:
	n = nx.get((p,c))
	if n is None:
		print(-1)
		exit()
	r,p = r+n,c
print(r)

### FIXED CODE ###

from bisect import bisect

s,t = input(),input()
n,x,nx,r = len(s),s+s,{},0

for i,c in enumerate(x):
	if nx.get(c) is None:
		nx[c] = []
	nx[c].append(i+1)

for c in t:
	l = nx.get(c)
	if l is None:
		print(-1)
		exit()
	r += l[bisect(l,r%n)]-r%n
print(r)
### BUGGY CODE ###

s=input()
n=len(s)
t=int(s)
dict={}
sum=0
for i in range(n):
    for j in range(i+1,n):
        string=str(i)+"_"+str(j)
        if string not in dict.keys():
            dict[string]=0
            num=s[i:j+1]
            num=int(num)
            if num%2019==0:
                sum+=1
        
print(sum)

### FIXED CODE ###

import sys
import collections as coun
sys.setrecursionlimit(10000000)
s=input()
n=len(s)
def mod10(x):
    return (10**(x%224))%2019
dp=[-1]*n
tmp=0
for i in reversed(range(n)):
    if i==n-1:
        dp[i]=int(s[i])
    else:
        dp[i]=(dp[i+1]+int(s[i])*pow(10,n-1-i,2019))%2019

#print(dp)
p=-1
for i in range(len(dp)-1):
    if dp[i]==dp[i+1]:
        dp[i]=p
        p=p-1

#print(dp)

c=coun.Counter(dp)
sum=0
for v in c.values():
    sum+=v*(v-1)//2
#print(sum)
for i in dp:
    if i==0:
        sum+=1
#print(sum)
if dp[-1]==0:
    sum=sum-1
print(sum)
### BUGGY CODE ###

K,S = map(int, input().split())

ans = 0
if K*3<S:
  print(0)
  exit()

for x in range(K, -1, -1):
  if x >S:
    continue
  for y in range(K, -1, -1):
    if x+y >S:
      continue
    for z in range(min(S-x-y, K), -1, -1):
      if x+y+z==S:
        ans+=1
      elif x+y+z<S:
        break

print(ans)

### FIXED CODE ###

K,S = map(int, input().split())

ans = 0
if K*3<S:
  print(0)
  exit()

for x in range(K, -1, -1):
  if x >S:
    continue
  for y in range(min(S-x, K), -1, -1):
    if x+y >S:
      continue
    for z in range(min(S-x-y, K), -1, -1):
      if x+y+z==S:
        ans+=1
      elif x+y+z<S:
        break

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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k=int(input())
ml=[i for i in range(k+1)]
n=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            if i==j==l:
                continue
            n+=gcd(i,j,l)         
print(n+sum(ml))

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k=int(input())
ml=[i for i in range(k+1)]
n=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            if i==j==l:
                continue
            n+=gcd(i,j,l)         
print(n+sum(ml))
### BUGGY CODE ###

X=int(input())

for i in range(31633000):
    for j in range(31622000):
        j *= -1
        if X == (i**5-j**5):
            print(i, j)
            exit()


### FIXED CODE ###

X=int(input())

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

import sys
import itertools
import bisect
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
l = na()

l.sort()

ct = 0
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            a = l[i]
            b = l[j]
            c = l[k]
            if a < b + c and b < a + c and c < a + b:
                ct += 1
print(ct)







### FIXED CODE ###

import sys
import itertools
import bisect
import math
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
l = na()

l.sort()

ct = 0
for i in range(n):
    for j in range(i+1, n):
        tmp = l[i] + l[j]
        ct += bisect.bisect_left(l, tmp) - (j + 1)
print(ct)
### BUGGY CODE ###

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

L, R = map(int, input().split())
hoge = set(list(range(L, R+1)))

for i in range(1, M):
    L, R = map(int, input().split())
    hoge = hoge & set(list(range(L, R+1)))

print(len(hoge))


### FIXED CODE ###

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

L, R = map(int, input().split())

for i in range(1, M):
    hoge, fuga = map(int, input().split())
    L = max(L, hoge)
    R = min(R, fuga)


if L > R:
    print(0)
else:
    print(R-L+1)
### BUGGY CODE ###

import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,q=mp()
tree=[[] for i in range(n+1)]
c=[0]*(n+1)
done=[0]*(n+1)
for i in range(n-1):
    a,b=mp()
    tree[a].append([a,b])
    tree[b].append([b,a])
for i in range(q):
    p,x=mp()
    c[p]+=x
que=deque()
que.append(tree[1])
done[1]=1
while len(que):
    q=que.popleft()
    for v in q:
        if done[v[1]]==0:
            done[v[1]]=1
            c[v[1]]+=c[v[0]]
            que.append(tree[v[1]])
print(*c[1:])

### FIXED CODE ###

import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,q=mp()
tree=[[] for i in range(n+1)]
c=[0]*(n+1)
done=[0]*(n+1)
for i in range(n-1):
    a,b=mp()
    tree[a].append([a,b])
    tree[b].append([b,a])
for i in range(q):
    p,x=mp()
    c[p]+=x
que=deque()
que.append(tree[1])
done[1]=1
while len(que):
    q=que.popleft()
    for v in q:
        if done[v[1]]==0:
            done[v[1]]=1
            c[v[1]]+=c[v[0]]
            que.append(tree[v[1]])
print(*c[1:])
### BUGGY CODE ###

n=int(input())
x=list(map(int,input().split()))
b=sorted(x)
m=(n-1+1)//2-1
for i in x:
    if b.index(i)<=m:print(b[m+1])
    else:print(b[m])

### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
b=sorted(x)
m=(n-1+1)//2-1
for i in x:
    if i<=b[m]:print(b[m+1])
    else:print(b[m])
### BUGGY CODE ###

def main():
  N =int(input())
  S = str(input())
  A = 0
  R = []
  G = []
  B = []
  for i in range(len(S)):
    if S[i] == "R":
      R.append(i+1)
    elif S[i] == "G":
      G.append(i+1)
    else:
      B.append(i+1)
  #print(R)
  #print(G)
  #print(B)

  for r in R:
    for g in G:
      for b in B:
        C = sorted([r,g,b])
        if C[1] - C[0] != C[2] - C[1]:
          A += 1
  print(A)
main()


### FIXED CODE ###

N =int(input())
S = str(input())
A = 0
R = []
G = []
B = []
for i in range(len(S)):
  if S[i] == "R":
    R.append(i+1)
  elif S[i] == "G":
    G.append(i+1)
  else:
    B.append(i+1)

A = len(R)*len(G)*len(B)
for i in range(N):
  for j in range(i+1,N):
    k = j + (j-i)
    if k >= N:
      break
    if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
      A -= 1
print(A)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A=[bin(a)[2:].zfill(60) for a in A]
ans=0
mod=10**9+7
for k in range(60):
    count=sum([int(a[k]) for a in A])
    ans+=count*(N-count)*(2**(60-k-1))
print(ans%mod)


### FIXED CODE ###

N=int(input())
A=[format(i,'060b') for i in map(int,input().split())]
ans=0
mod=10**9+7
for k in range(60):
    count=[a[60-1-k] for a in A].count('0')
    ans+=count*(N-count)*(2**k)%mod
print(ans%mod)
### BUGGY CODE ###

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

def calc(a):
    s = 0
    x = 0
    for i in a:
        s += abs(i - x)
        x = i
    s += abs(0 - x)
    print(s)

for i in range(n):
    temp = a[:]
    del temp[i]
    calc(temp)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
s = 0
a.insert(0, 0)
a.insert(n+1, 0)
for j in range(n+1):
    s += abs(a[j] - a[j+1])
for i in range(1, n+1):
    s_i = s + abs(a[i-1]-a[i+1]) - ((abs(a[i-1] - a[i]) + abs(a[i]-a[i+1])))
    print(s_i)
### BUGGY CODE ###

N = int(input())
A = 0
B = 0
BA = 0
num = 0
for i in range(N):
    k = input()
    if k[0] == 'B' and k[-1] == 'A':
        BA += 1
    elif k[0] == 'B':
        B += 1
    elif k[-1] == 'A':
        A += 1

    for j in range(N - 1):
        if k[j:j + 2] == 'AB':
            num += 1

num += max(0, BA - 1)
BA -= max(0, BA - 1)
num += min(BA, A) + min(BA, B)
A -= min(BA, A)
B -= min(BA, B)
num += min(A, B)
print(num)




### FIXED CODE ###

N = int(input())
A = 0
B = 0
BA = 0
num = 0
for i in range(N):
    k = input()
    if k[0] == 'B' and k[-1] == 'A':
        BA += 1
    elif k[0] == 'B':
        B += 1
    elif k[-1] == 'A':
        A += 1

    for j in range(len(k) - 1):
        if k[j:j + 2] == 'AB':
            num += 1

num += max(0, BA - 1)
BA -= max(0, BA - 1)
num += min(BA, A) + min(BA, B)
A -= min(BA, A)
B -= min(BA, B)
num += min(A, B)
print(num)
### BUGGY CODE ###

#Python

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


b=[]
for i in range(N-1):
	i=i+1
	#print "x::"+str(sum(a[:i]))
	#print "sum-2x::"+str( abs( sum(a) - sum(a[:i])*2 ) )
	b.append( abs( sum(a) - sum(a[:i])*2 ) )

#print b
print min(b)


### FIXED CODE ###

#Python

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

b=[]
ans=0
sum=sum(a)

x=0
for i in range(N-1):
	x+=a[i]
	#print "x::"+str(x)
	if i==0:
		ans= abs( sum - x*2 )
	if ans>abs( sum - x*2 ):
		ans= abs( sum - x*2 )
	#print "ans::"+str(ans)

print ans
### BUGGY CODE ###

n = int(input())
S = input()
sum_i = [n - 1] * n
for i in range(n):
    sum_i[i] = S[:i].count('W') + S[i + 1:].count('E')

print(min(sum_i))


### FIXED CODE ###

n = int(input())
S = input()
e_sum = [0] * n
w_sum = [0] * n
ew_sum = [0] * n
for i in range(2, n + 1):
    e_sum[-i] = e_sum[-i + 1] + 1 if S[-i + 1] == 'E' else e_sum[-i + 1]
    ew_sum[-i] = e_sum[-i]
for i in range(1, n):
    w_sum[i] = w_sum[i - 1] + 1 if S[i - 1] == 'W' else w_sum[i - 1]
    ew_sum[i] += w_sum[i]

print(min(ew_sum))
### BUGGY CODE ###

import sys

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1
        else:
            tmp += 2
        continue

    M = M // tmp
    factor[tmp] = factor.get(tmp, 0) + 1

if(factor == {}):
    print(1)
    sys.exit()

ans = 1
max_a = 7 + 10 ** 9
max_value = max(list(factor.values()))
aho = {0: 1}
fact = {0: 1}
abc = {}
for i in range(1, max_value + 1):
    # print(i)
    aho[i] = ((aho[i - 1] * (i + N - 1)))
    fact[i] = (fact[i - 1] * i)
    abc[i] = (aho[i] // fact[i]) % max_a


# print(factor)
# print(aho, fact)
for i in factor.values():
    # print(i)
    ans = (ans * abc[i]) % max_a
print(ans)

### FIXED CODE ###

import sys

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

factor = {}
tmp = 2
while(M // tmp >= 1):
    if(M % tmp != 0):
        if(tmp == 2):
            tmp += 1
        elif(M // tmp < tmp):
            tmp = M
        else:
            tmp += 2
        continue

    M = M // tmp
    factor[tmp] = factor.get(tmp, 0) + 1

if(factor == {}):
    print(1)
    sys.exit()

ans = 1
max_a = 7 + 10 ** 9
max_value = max(list(factor.values()))
aho = {0: 1}
fact = {0: 1}
abc = {}
for i in range(1, max_value + 1):
    # print(i)
    aho[i] = ((aho[i - 1] * (i + N - 1)))
    fact[i] = (fact[i - 1] * i)
    abc[i] = (aho[i] // fact[i]) % max_a


# print(factor)
# print(aho, fact)
for i in factor.values():
    # print(i)
    ans = (ans * abc[i]) % max_a
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
a = set()
for i in range(n-2):
  for j in range(i+1,n-1):
    a = a|set([s[i]+s[j]+k for k in set(list(s[j+1:]))])
print(len(a))

### FIXED CODE ###

n = int(input())
s = input()
a = set()
a1 = []
for i in range(n-2):
  if s[i] in a1:
    continue
  a1.append(s[i])
  a2 = []
  for j in range(i+1,n-1):
    if s[j] in a2:
      continue
    a2.append(s[j])
    a = a|set([s[i]+s[j]+k for k in set(list(s[j+1:]))])
print(len(a))
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline

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

    tmp=[0,0,0]
    cnt=0
    for i in range(0,1000):
        if i < 10:
            tmp[0]=0
            tmp[1]=0
            tmp[2]=i
        elif i < 100:
            tmp[0]=0
            tmp[1]=i//10
            tmp[2]=i-tmp[1]*10
        else:
            tmp[0]=i//100
            tmp[1]=(i-tmp[0]*100)//10
            tmp[2]=i-tmp[0]*100-tmp[1]*10
        ketaflg=0
        for j in s :
            if j == '\n':
                break
            if tmp[0]==int(j) and ketaflg==0:
                ketaflg=1
            elif tmp[1]==int(j) and ketaflg==1:
                ketaflg=2
            elif tmp[2]==int(j) and ketaflg==2:
                ketaflg=3
                cnt+=1
                break
    print(cnt)


if __name__=='__main__':
    main()


### FIXED CODE ###

import sys

def main():
    # input = sys.stdin.readline

    n=int(input())
    s=list(map(int,input()))
    # s.pop(-1)
    cnt=0
    for i in range(10):
        if i in s[:-2]:
            idx1=s[:-2].index(i)
            for j in range(10):
                if j in s[idx1+1:-1]:
                    idx2=s[idx1+1:-1].index(j)+idx1+1
                    for k in range(10):
                        if k in s[idx2+1:]:
                            cnt+=1
    print(cnt)

    #
    # tmp=[0,0,0]
    # cnt=0
    # for i in range(0,1000):
    #     if i < 10:
    #         tmp[0]=0
    #         tmp[1]=0
    #         tmp[2]=i
    #     elif i < 100:
    #         tmp[0]=0
    #         tmp[1]=i//10
    #         tmp[2]=i-tmp[1]*10
    #     else:
    #         tmp[0]=i//100
    #         tmp[1]=(i-tmp[0]*100)//10
    #         tmp[2]=i-tmp[0]*100-tmp[1]*10
    #     ketaflg=0
    #     for j in s :
    #         if j == '\n':
    #             break
    #         if tmp[0]==int(j) and ketaflg==0:
    #             ketaflg=1
    #         elif tmp[1]==int(j) and ketaflg==1:
    #             ketaflg=2
    #         elif tmp[2]==int(j) and ketaflg==2:
    #             ketaflg=3
    #             cnt+=1
    #             break
    # print(cnt)


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

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

idx = 1
idx_count = 0
idx_set = []
for i in range(N):
  if idx != B[i]:
    tmp1 = int(idx_count*(idx_count-1)/2)		# あるボールの等価な組み合わせ数
    tmp2 = int((idx_count-1)*(idx_count-2)/2)	# あるボールを1つ除いたときの等価な組み合わせ数
    idx_set.append([idx, tmp1, tmp2])
    idx_count = 0
    idx = B[i]
  idx_count+=1
if idx_count != 0:
  tmp1 = int(idx_count*(idx_count-1)/2)		# あるボールの等価な組み合わせ数
  tmp2 = int((idx_count-1)*(idx_count-2)/2)	# あるボールを1つ除いたときの等価な組み合わせ数
  idx_set.append([idx, tmp1, tmp2])
#print(idx_set)

for i in range(N):
  tmp = 0
  for j in range(len(idx_set)):
    if A[i] == idx_set[j][0]:
      tmp += idx_set[j][2]
    else:
      tmp += idx_set[j][1]
  print(tmp)



### FIXED CODE ###

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

for i in range(N):
  B[A[i]]+=1
#print(B)

all_c = 0
for i in range(1,N+1):
  all_c += int(B[i]*(B[i]-1)/2)			# 同一の整数を持つボールの組合せ数
for i in range(N):
  if B[A[i]] != 0:
    print(int(all_c-(B[A[i]]-1)))
### BUGGY CODE ###

N,M,*a=map(int,open(0).read().split())
dp=[0]*(N+1)
dp[0]=1
if 1 in a:
    dp[1]=0
else:
    dp[1]=1
for i in range(2,N+1):
    if i in a:
        continue
    dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%1000000007)    


### FIXED CODE ###

N,M=map(int,input().split())
dp=[1]*(N+1)
for i in range(M):
    dp[int(input())]=0
for i in range(2,N+1):
    if dp[i]!=0:
        dp[i]=(dp[i-1]+dp[i-2])
print(dp[-1]%1000000007)
### BUGGY CODE ###

N, K = map(int, raw_input().split())
l = map(int, raw_input().split())

s = list(set(l))
num = range(len(s))
if len(s) <= K: print 0
else:
    for i in range(len(s)):
        num[i] = l.count(s[i])
    sousa = len(s)-K
    num.sort()
    print sum(num[:sousa])


### FIXED CODE ###

#!/usr/bin/python
#coding: utf-8

from collections import Counter

N, K = map(int, raw_input().split())
l = map(int, raw_input().split())

s = list(set(l))
num = range(len(s))
if len(s) <= K: print 0
else:
    counter = Counter(l)
    nums = counter.values()
    sousa = len(s)-K
    nums.sort()
    print sum(nums[:sousa])
### BUGGY CODE ###


N,Q=[int(i) for i in input().rstrip().split()]
S = input().strip()
lr_list=[[int(j) for j in input().split()] for i in range(Q)]

for l,r in lr_list:
    sub_str = S[(l-1):r]
    cnt = sub_str.count("AC")
    print(cnt)


### FIXED CODE ###

N,Q=[int(i) for i in input().rstrip().split()]
S = input().strip()
lr_list=[[int(j) for j in input().split()] for i in range(Q)]

calc_cnt=[0]
for i in range(1,len(S)):
    sub_str = S[(i-1):(i+1)]
    
    if sub_str == "AC":
        calc_cnt += [calc_cnt[i-1] + 1]
    else:
        calc_cnt += [calc_cnt[i-1]]
        

for l,r in lr_list:
    ans = calc_cnt[r-1] - calc_cnt[l-1]
    print(ans)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())
cnt = 0

for i in range(n+1):
    for j in range(n+1):
        a = n - r*i - g*j
        if a >= 0 and a % b == 0:
            cnt += 1

print(cnt)

### FIXED CODE ###

r, g, b, n = map(int, input().split())
cnt = 0
 
for i in range(n+1):
    for j in range(n-i+1):
        a = n - r*i - g*j
        if a >= 0 and a % b == 0:
            cnt += 1
 
print(cnt)
### BUGGY CODE ###

def main():
    n, m = list(map(int, input().split()))
    root_start = []
    root_goal = []
    for i in range(m):
        li = list(map(int, input().split()))
        if li[0] == 1:
            root_start.append(li[1])
        elif li[1] == n:
            root_goal.append(li[0])
    flg = False
    for ls in root_start:
        if ls in root_goal:
            flg = True

    print('POSSIBLE') if flg else print('IMPOSSIBLE')



if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, m = list(map(int, input().split()))
    root_start = []
    root_goal = []
    ans = {}
    for i in range(m):
        li = list(map(int, input().split()))
        if li[0] == 1:
            ans.setdefault(li[1], 0)
            ans[li[1]] += 1
        elif li[1] == n:
            ans.setdefault(li[0], 0)
            ans[li[0]] += 1
    flg = False
    for k in ans:
        if ans[k] >= 2:
            flg = True

    print('POSSIBLE') if flg else print('IMPOSSIBLE')



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

#D
n = int(input())
s = input()
s_l = tuple(s)
cnt = 0
for i in range(n-2):
    for j in range(i,n-1):
        if s_l[i] != s_l[j]:
            for k in range(j,n):
                if s_l[i] != s_l[k] and s_l[j] != s_l[k] and j-i != k-j:
                    cnt += 1

print(cnt)
     

### FIXED CODE ###

#D
n = int(input())
s = input()
s_l = list(s)

a = s_l.count('R') * s_l.count('G') * s_l.count('B')
cnt = 0
#i,j,kがそれぞれ異なり、j-i = k-jであるものを求める
for i in range(n-2):
    for j in range(i,n-1):
        if 2*j - i < n:
            if s_l[i] != s_l[j] and s_l[i] != s_l[2*j-i] and s_l[j] != s_l[2*j-i]:
                cnt += 1
                
print(a - cnt)