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

n,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(set(a))
res = 0
if len(b) <= k:
  print(0)
else:
  if k <= n / 2:
    tmp = [0] * k
    for i in b:
      a_count = a.count(i)
      if a_count > tmp[0]:
        tmp.pop(0)
        tmp.append(a_count)
        tmp.sort()
    for i in range(k):
      res = res + tmp[i]
    print(n - res)
  else:
    tmp = [200000] * (n - k)
    for i in b:
      a_count = a.count(a)
      if a_count < tmp[0]:
        tmp.pop(0)
        tmp.append(a_count)
        tmp.sort(reverse=True)
    for i in range(n - k):
      res = res + tmp[i]
    print(res)

### FIXED CODE ###

from collections import Counter
n,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(set(a))
if len(b) <= k:
  print(0)
else:
  c = sorted(Counter(a).values(), reverse=True)
  print(sum(c[k:]))
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
lis = sorted(x)

#ans = []
for i in x:
    keylist = lis[:lis.index(i)]+lis[lis.index(i)+1:]
    #print(keylist)
    ans = keylist[n//2-1]
    print(ans)


### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
lis = sorted(x)
key1 = lis[n//2-1]
key2 = lis[n//2]
for i in x:
    if i > key1:
        print(key1)
    else:
        print(key2)
### BUGGY CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for i in range(n+1)]
for i in range(m+1):
	dp[0][i]=1
for j in range(n+1):
	dp[j][0]=1
for i in range(n):
	for j in range(m):
		if s[i]==t[j]:
			dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%1000000007
		else:
			dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j]-dp[i][j])%1000000007
print(dp[n][m])

### FIXED CODE ###

n,m=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
dp=[[0 for i in range(m+1)] for i in range(n+1)]
for i in range(m+1):
	dp[0][i]=1
for j in range(n+1):
	dp[j][0]=1
for i in range(n):
	for j in range(m):
		if s[i]==t[j]:
			dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j])%1000000007
		else:
			dp[i+1][j+1]=(dp[i][j+1]+dp[i+1][j]-dp[i][j])%1000000007
print(dp[n][m])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
#A = sorted(A)
#B = sorted(B)
C = sorted(C)
answer = 0
for i in range(N) :
    for j in range(N) :
        if A[i] < B[j] :
            for k in range(N) :
                if B[j] < C[k] :
                    answer += N-(k+1)+1
                    break
print(answer)
                

### FIXED CODE ###

import bisect
def main() :
    N = int(input())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))
    C = list(map(int,input().split()))
    A.sort()
    B.sort()
    C.sort()
    answer = 0
    for b in B :
        i = bisect.bisect_left(A,b)
        j = bisect.bisect_right(C,b)
        if i > 0 and j != len(C) :
            answer += i * (N-j)
    print(answer)
main()
### BUGGY CODE ###

#python3

INF = int(1e9)

def main():

    n, k = map(int, input().split()) 
    h = [int(i) for i in input().split()] + [0]* 110


    dp = [INF] * 100001
    dp[0] = 0
    for i in range(n):
        for j in range(1, k+1):
            if i >= j:
                dp[i] = min(dp[i] , dp[i-j] + abs(h[i-j]- h[i])) 

    print(dp[n-1])

main() 

### FIXED CODE ###

#python3

INF = int(1e9)

def main():

    n, k = map(int, input().split()) 
    h = [int(i) for i in input().split()] + [0]* 110


    dp = [INF] * 110000
    dp[0] = 0
    for i in range(n):
        for j in range(1, k+1):
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]))

    print(dp[n-1])

main()
### BUGGY CODE ###

import collections
import copy

N = int(input())
B = list(map(int, input().split()))
temp = 0

setB = list(set(B))
num = len(setB)

for i in range(N):
  newB = copy.copy(B)
  newB[i] = 0
  res = 0
  for j in range(num):
    res += newB.count(setB[j])*(newB.count(setB[j])-1)/2
  print(int(res))

### FIXED CODE ###

N = int(input())
B = list(map(int, input().split()))
count = {}

for i in B:
  if i in count:
    count[i] += 1
  else:
    count[i] = 1
    
total = 0
for i in count:
  total += count[i]*(count[i]-1)/2
  
for i in range(N):
  k = count[B[i]]
  print(int(total-k+1))
### BUGGY CODE ###

a, b, k = map(int, input().split())
for i in range(a, min(a + k, b)) :
        if a <= i < a + k :
                print(i)
for i in range(min(a + k, b), b + 1) :
        if b - k < i :
                print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
if k > (b - a)//2 :
	for i in range(a, b+1) :
		print(i)   
	exit()
for i in range(a, a + k) :          
	if a <= i < a + k :
		print(i)
for i in range(b - k, b + 1) :
	if b - k < i and a + k <= i:
		print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
K,S=map(int,input().split())
count=0
for i in range(K+1):
  for j in range(K+1):
    for k in range(K+1):
      if i+j+k==S:
        count=count+1
print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
K,S=map(int,input().split())
count=0
for i in range(K+1):
  for j in range(K+1):
    k=S-i-j
    if 0<=k<=K:
      count=count+1
print(count)
### BUGGY CODE ###

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

b = []

for i in range(100000):
    b.append(a.count(i-1) + a.count(i) + a.count(i+1))

print(max(b))


### FIXED CODE ###

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

b = []
c = []
for i in range(N):
    if a[i] > 0:
        b.append(a[i] - 1)
        c.append(a[i] + 1)
    else:
        c.append(a[i] + 1)

abc = a + b + c
count = [0] * (max(abc) + 1)

for x in abc:
    count[x] += 1

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

from collections import deque
import sys

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

flag = [ [False] * N for i in range(N) ]
crash = [False] * N
cost = [float("-inf")] * N
cost[0] = 0

dic = {}
for i in range(N):
    dic[i] = []

    

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    dic[A].append([B,C-P])

q = deque([0])

cnt = 0

while len(q) > 0:

    now = q.popleft()

    for bc in dic[now]:
    
        b = bc[0]
        c = bc[1]

        #print (now,b,flag[now],crash[now],flag[b],crash[b])

        if b == N-1 and crash[now]:
            print (-1)
            sys.exit()

        if cost[now] + c > cost[b] or crash[now]:


            if flag[now][b] and not crash[b]:

                crash[b] = True

                cost[b] = cost[now] + c

                flag[b] = flag[now].copy()

                for j in range(N):

                    flag[b][j] = flag[now][j]
                flag[b][b] = True
            
                q.append(b)

            elif not flag[now][b]:
                
                cost[b] = cost[now] + c
                crash[b] = crash[now]
                cost[b] = cost[now] + c
                crash[b] = crash[now]

                flag[b] = flag[now].copy()
                    
                flag[b][b] = True

                q.append(b)

            else:

                if not crash[b]:
                    crash[b] = crash[now]
                    q.append(b)
                

    cnt += 1

    if cnt > M*N:
        print (-1)
        sys.exit()

print (max(0,cost[N-1]))
    


### FIXED CODE ###


"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

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

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))
### BUGGY CODE ###

# ABC144E - Gluttony
def binary_search(upper_lim: int) -> int:
    ok, ng = upper_lim, -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    return ok


def check(x: int) -> bool:
    cost = sum(a - x // f for a, f in zip(A, F) if a * f > x)
    return cost <= K


def main():
    global K, A, F
    N, K, *AF = map(int, open(0).read().split())
    A, F = AF[:N], AF[N:]
    A.sort(), F.sort(reverse=1)
    ans = binary_search(A[-1] * F[0] + 1)
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ABC144E - Gluttony
def binary_search(upper_lim: int) -> int:
    ok, ng = upper_lim, -1
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    return ok


def check(x: int) -> bool:
    cost = sum(a - x // f for a, f in zip(A, F) if a * f > x)
    return cost <= K


def main():
    global K, A, F
    N, K, *AF = map(int, open(0).read().split())
    A, F = AF[:N], AF[N:]
    A.sort(), F.sort(reverse=1)
    ans = binary_search(A[-1] * F[0] + 1)
    print(ans)


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

P = 10**9+7

fact = [1 for _ in range(2000001)]
inv = [1 for _ in range(2000001)]
fact_inv = [1 for _ in range(2000001)]

for i in range(2, 2000001):
    fact[i] = (fact[i-1]*i) % P
    inv[i] = P - (inv[P % i] * (P // i)) % P
    fact_inv[i] = (fact_inv[i-1] * inv[i]) % P

K = int(input())
S = input()
N = K + len(S)
ans = 0
for i in range(K+1):
    ans += pow(25, i, P) * (fact[N] * fact_inv[N-i] * fact_inv[i] % P)
    ans = ans % P

print(ans)

### FIXED CODE ###

P = 10**9+7

fact = [1 for _ in range(2000001)]
inv = [1 for _ in range(2000001)]
fact_inv = [1 for _ in range(2000001)]

for i in range(2, 2000001):
    fact[i] = (fact[i-1]*i) % P
    inv[i] = P - (inv[P % i] * (P // i)) % P
    fact_inv[i] = (fact_inv[i-1] * inv[i]) % P

K = int(input())
S = input()
N = K + len(S)
p = 1
ans = 0
for i in range(K+1):
    ans += p * (fact[N] * fact_inv[N-i] * fact_inv[i] % P)
    ans = ans % P
    p *= 25
    p = p % P

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

n = int(input())
A = list(map(int,input().split()))
s = sum(A)
Q = int(input())
for _ in range(Q):
    B,C = map(int,input().split())
    if B in A:
        c = A.count(B)
        A = [C if i == B else i for i in A]
        s = s-((B-C)*c)

    print (s)


### FIXED CODE ###

n = int(input())
A = {}
a = list(map(int,input().split()))
for i in a:
    if not i in A:
        A[i] = 1
    else:
        A[i] += 1

s = 0
for k,v in A.items():
    s += k*v

Q = int(input())
for _ in range(Q):
    b,c = map(int,input().split())
    if b in A:
        s = s-(b-c)*A[b]
        if not c in A:
            A[c] = A[b]
        else:
            A[c] += A[b]
        A[b] = 0

    print (s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
nF = list(map(str, input().split('T')))
finalx, finaly = list(map(int, input().split()))

x = []
y = []
for i in range(len(nF)):
    if i % 2 == 0:
        x.append(len(nF[i]))
    else:
        y.append(len(nF[i]))

posy = [0]
if len(x) == 0:
    posx = [0]
elif len(x) == 1:
    posx = [x[0]]
else:
    posx = [x[0]]
    for i in range(1, len(x)):
        plus_x = list(map(lambda elem: elem + x[i], posx))
        minus_x = list(map(lambda elem: elem - x[i], posx))
        plus_x.extend(minus_x)
        posx = plus_x

if len(y) >= 1:
    for i in range(len(y)):
        plus_y= list(map(lambda elem: elem + y[i], posy))
        minus_y= list(map(lambda elem: elem - y[i], posy))
        plus_y.extend(minus_y)
        posy = plus_y

if finalx in posx and finaly in posy:
    print('Yes')
else:
    print('No')



### FIXED CODE ###

# -*- coding: utf-8 -*-
nF = list(map(str, input().split('T')))
finalx, finaly = list(map(int, input().split()))

x = []
y = []
for i in range(len(nF)):
    if i % 2 == 0:
        x.append(len(nF[i]))
    else:
        y.append(len(nF[i]))

posy = [0]
if len(x) == 0:
    posx = [0]
elif len(x) == 1:
    posx = [x[0]]
else:
    posx = [x[0]]
    for i in range(1, len(x)):
        plus_x = list(map(lambda elem: elem + x[i], posx))
        minus_x = list(map(lambda elem: elem - x[i], posx))
        plus_x.extend(minus_x)
        posx = list(set(plus_x))

if len(y) >= 1:
    for i in range(len(y)):
        plus_y= list(map(lambda elem: elem + y[i], posy))
        minus_y= list(map(lambda elem: elem - y[i], posy))
        plus_y.extend(minus_y)
        posy = list(set(plus_y))

if finalx in posx and finaly in posy:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

from collections import defaultdict
import itertools


def analyze(string):
  s_count = defaultdict(int)
  for s in string:
    s_count[s] += 1
  return s_count

def count_up(s_count):
  strings = list(s_count.keys())
  ans = 0
  for num in range(1, len(strings) + 1):
    for s_list in itertools.combinations(strings, num):
      a = 1
      for s in s_list:
        a *= s_count[s]
      ans += a
  print(ans % (10**9 + 7))

N = int(input())
string = input()

s_count = analyze(string)
count_up(s_count)


### FIXED CODE ###

from collections import defaultdict
import itertools
from functools import reduce


def analyze(string):
  s_count = defaultdict(int)
  for s in string:
    s_count[s] += 1
  counts = tuple(s_count.values())
  return counts

N = int(input())
string = input()

def search(N, string):
    memo = {}
    def count(counts, num_set):
        if (counts, num_set) in memo:
            return memo[(counts, num_set)]

        if num_set == 1:
            ans = sum(counts)
        elif num_set == 2:
            num_sum = sum(counts)
            ans = 0
            for i in range(len(counts)):
                num_sum -= counts[i]
                ans += counts[i] * num_sum
        else:
            ans = 0
            for i in range(len(counts) - 1):
                ans += counts[i] * count(counts[i + 1:], num_set - 1)

        memo[(counts, num_set)] = ans
        return ans

    counts = analyze(string)
    ans = 0
    for i in range(1, len(counts) + 1):
        ans += count(counts, i)
    print(ans % (10**9 + 7))

search(N, string)
### BUGGY CODE ###

l=input()
n=len(l)
mod=1000000007
dp=[0]*n
dp[0]=2
ans=[0]*n
ans[0]=(3**(n-1))%mod
for i in range(1,n):
  if l[i]=='0':
    dp[i]=dp[i-1]
    ans[i]=ans[i-1]
  else:
    dp[i]=(dp[i-1]*2)%mod
    ans[i]=(ans[i-1]+dp[i-1]*(3**(n-i-1)))%mod
print((ans[n-1]+dp[n-1])%mod)


### FIXED CODE ###

l=input()
n=len(l)
mod=1000000007
dp=[0]*n
dp[0]=2
ans=[0]*n
ans[0]=1
for i in range(1,n):
  if l[i]=='0':
    dp[i]=(dp[i-1])%mod
    ans[i]=(ans[i-1]*3)%mod
  else:
    dp[i]=(dp[i-1]*2)%mod
    ans[i]=(ans[i-1]*3+dp[i-1])%mod
print((ans[n-1]+dp[n-1])%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*n
dp[0] = 0
for i in range(n):
    for j in range(1, k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))
print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [float('inf')]*n
dp[0] = 0
for i in range(n):
    for j in range(1, k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))
print(dp[n-1])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*n
b[0] = a[0]
for i in range(1, n):
    b[i] = b[i-1] ^ a[i]
    a[i] += a[i-1]

a.insert(0, 0)
b.insert(0, 0)

ans = 0
for i in range(0, n+1):
    for j in range(i+1, n+1):
        x = a[j]-a[i]
        y = b[j]^b[i]
        if x==y:
            ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
p = 0
used = False
count = 1
for i in range(n):
    if a[i]^p == a[i]+p:
        if used:
            count += 1
        used = True
        p += a[i]
    else:
        c = count
        for j in range(i-c, i):
            count -= 1
            p -= a[j]
            if p^a[i] == p+a[i]:
                break
        if count == 0:
            p = a[i]
            count = 1
        else:
            count += 1
            p += a[i]
    ans += count
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * len(D)
    XST.sort(reverse=True)
    for x, s, t in XST:
        s0 = bisect_left(D, s)
        t0 = bisect_left(D, t)
        for i in range(s0, t0):
            ans[i] = x
    for y in ans:
        print(y)
    return

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect_left

def main():
    N, Q = LI()
    XST = []
    for _ in range(N):
        s, t, x = LI()
        s -= x
        t -= x
        XST.append([x, s, t])
    D = []
    for _ in range(Q):
        D.append(II())
    ans = [-1] * Q
    nexts = [-1] * Q
    XST.sort()
    for x, s, t in XST:
        i = bisect_left(D, s)
        end = bisect_left(D, t)
        while i < end:
            if nexts[i] == -1:
                ans[i] = x
                nexts[i] = end
                i += 1
            else:
                i = nexts[i]
    for y in ans:
        print(y)
    return

main()
### BUGGY CODE ###

from collections import deque

ni = lambda: int(input())
nm = lambda: map(int, input().split())
# nl = lambda: list(map(int, input().split()))

n,x,y=nm()

class Node:
  def __init__(self,x):
    self.val = x
    self.left=[]
    self.right=[]

nodes = [Node(i) for i in range(n)]
for i in range(n-1):
  nodes[i].right.append(nodes[i+1])
  nodes[i+1].left.append(nodes[i])

nodes[x-1].right.append(nodes[y-1])
nodes[y-1].left.append(nodes[x-1])

gl_dist = [0]*n


for i in range(n):
  dist = [-1]*n
  dist[i]=0
  q = deque()
  q.append(nodes[i])
  while len(q) > 0:
    node = q.popleft()
    nv = node.val
    nl = node.left
    nr = node.right

    for nli in nl:
      if dist[nli.val] == -1:
        dist[nli.val] = dist[nv]+1
        q.append(nli)
    for nri in nr:
      if dist[nri.val] == -1:
        dist[nri.val] = dist[nv]+1
        q.append(nri)

  for j in range(i+1,n):
    # print("{} to {} is {}".format(i,j,dist[j]))
    if dist[j] != -1:
      gl_dist[dist[j]]+=1

for i in range(1,n):
  print(gl_dist[i])
# print(gl_dist)


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n,x,y = nm()

dist = [0]*n

for i in range(1,n+1):
  for j in range(i+1,n+1):
    naive = j-i
    cand = naive
    if i<x:
      if x<=j<=y:
        cand = x-i+1+y-j
      elif j>y:
        cand = x-i+1+j-y
    elif x<=i<=y:
      if j<=y:
        cand = i-x+1+y-j
      else:
        cand = i-x+1+j-y
    d = min(naive,cand)
    dist[d]+=1

for i in range(1,n):
  print(dist[i])
### BUGGY CODE ###

param_n = int(input())
params1 = list(map(lambda x: int(x), input().split(' ')))

for i in range(param_n):
    print(len(list(filter(lambda x: x == i + 1, params1))))

### FIXED CODE ###

param_n = int(input())
params1 = list(map(lambda x: int(x), input().split(' ')))

result = [0 for i in range(param_n)]

for employee in params1:
    result[employee - 1] += 1

for num in result:
    print(num)
### BUGGY CODE ###

h,w,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
H=[0]*h
W=[0]*w
for i in range(m):
  H[l[i][0]-1]+=1
  W[l[i][1]-1]+=1
hmax=max(H)
wmax=max(W)
cthmax=0
ctwmax=0
for i in range(h):
  if H[i]==hmax:
    cthmax+=1
for i in range(w):
  if W[i]==wmax:
    ctwmax+=1
ct=0
for i in range(m):
  if H[l[i][0]-1]==max(H) and W[l[i][1]-1]==max(W):
    ct+=1
if cthmax*ctwmax>ct:
  print(hmax+wmax)
else:
  print(hmax+wmax-1)

### FIXED CODE ###

h,w,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
H=[0]*h
W=[0]*w
for i in range(m):
  H[l[i][0]-1]+=1
  W[l[i][1]-1]+=1
hmax=max(H)
wmax=max(W)
cthmax=0
ctwmax=0
for i in range(h):
  if H[i]==hmax:
    cthmax+=1
for i in range(w):
  if W[i]==wmax:
    ctwmax+=1
ct=0
for i in range(m):
  if H[l[i][0]-1]==hmax and W[l[i][1]-1]==wmax:
    ct+=1
if cthmax*ctwmax>ct:
  print(hmax+wmax)
else:
  print(hmax+wmax-1)
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

num = [i for i in range(1, N)]
print(sum(num))

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

# print(int(N*(N - 1)/2))
if N%2 == 0:
	print((ceil(N/2) - 1)*N + N//2)
else:
	print((ceil(N/2) - 1)*N)
### BUGGY CODE ###

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

# process
R, G, B = [], [], []
for i, s in enumerate(list(S)):
    if s == 'R':
        R.append(i)
    elif s == 'G':
        G.append(i)
    else:
        B.append(i)

ans = len(R)*len(G)*len(B)
for r in R:
    for g in G:
        i, j = r, g
        if i > j:
            i, j = j, i
        
        s = j-i
        t1 = i-s
        t2 = -1
        if s%2 == 0:
            t2 = i+s//2
        t3 = j+s
        
        k = 0
        while k < len(B) and B[k] < t1:
            k += 1
        if k == len(B):
            continue
        if B[k] == t1:
            ans -= 1
        
        if t2 != -1:
            while k < len(B) and B[k] < t2:
                k += 1
            if k == len(B):
                continue
            if B[k] == t2:
                ans -= 1

        while k < len(B) and B[k] < t3:
            k += 1
        if k == len(B):
            continue
        if B[k] == t3:
            ans -= 1

# output
print(ans)


### FIXED CODE ###

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

# process
ans = S.count('R')*S.count('G')*S.count('B')
for i in range(N):
    for j in range(N):
        if i-j<0 or i+j >= N:
            break
        x = S[i-j]
        y = S[i]
        z = S[i+j]

        if x!= y and x != z and y != z:
            ans -= 1
            
# output
print(ans)