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

input()
A = [int(_) for _ in input().split()]
A = [A[0]] + [j for i, j in zip(A, A[1:]) if i >= j]
N = len(A)


def cut(array, index):
    if index < 1:
        return []
    for _ in range(len(array)):
        if index <= array[_][0]:
            return array[:_] + [(index, array[_][1])]


def is_possible(K):
    dp = [(A[0], 0)]
    for a in A[1:]:
        if a <= dp[-1][0]:
            dp = cut(dp, a)
        else:
            dp += [(a, 0)]
        is_added = False
        for j in range(len(dp) - 1, -1, -1):
            if dp[j][1] < K - 1:
                dp = cut(dp, dp[j][0] - 1) + [(dp[j][0], dp[j][1] + 1)]
                if dp[-1][0] < a:
                    dp += [(a, 0)]
                is_added = True
                break
        if not is_added:
            return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))


### FIXED CODE ###

import random
input()
A = [int(_) for _ in input().split()]
A = [A[0]] + [j for i, j in zip(A, A[1:]) if i >= j]
N = len(A)


def cut(array, index):
    if index < 1:
        return []
    if index <= array[0][0]:
        return [(index, array[0][1])]
    for _ in range(len(array)-1, 0, -1):
        if array[_ - 1][0] < index:
            return array[:_] + [(index, array[_][1])]


def is_possible(K):
    dp = [(A[0], 0)]
    for a in A[1:]:
        if a <= dp[-1][0]:
            dp = cut(dp, a)
        else:
            dp += [(a, 0)]
        is_added = False
        for j in range(len(dp) - 1, -1, -1):
            if dp[j][1] < K - 1:
                dp = cut(dp, dp[j][0] - 1) + [(dp[j][0], dp[j][1] + 1)]
                if dp[-1][0] < a:
                    dp += [(a, 0)]
                is_added = True
                break
        if not is_added:
            return False
    return True


def bis(x, y):
    if y == x + 1:
        return y
    elif is_possible((x + y) // 2):
        return bis(x, (x + y) // 2)
    else:
        return bis((x + y) // 2, y)


print(bis(0, N))
### 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)
    for v in d[1]:
        d[v].remove(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()
        for v in d[node]:
            d[v].remove(node)
        ans *= perm_list[len(d[node])]
        stack |= d[node]
    return ans
    
print(main() % 1000000007)

### 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 ###

n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
y=[l[i][1] for i in range(n)]
ans=[]
for i1 in range(n):
  for i2 in range(i1+1,n):
    for i3 in range(n):
      for i4 in range(i3+1,n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))

### FIXED CODE ###

n,k=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
x=[l[i][0] for i in range(n)]
x.sort()
y=[l[i][1] for i in range(n)]
y.sort()
ans=[]
for i1 in range(n):
  for i2 in range(i1,n):
    for i3 in range(n):
      for i4 in range(i3,n):
        ct=0
        for i5 in range(n):
          if min(x[i1],x[i2])<=l[i5][0]<=max(x[i1],x[i2]) and min(y[i3],y[i4])<=l[i5][1]<=max(y[i3],y[i4]):ct+=1
        if ct>=k:
          ans.append(abs(x[i1]-x[i2])*abs(y[i3]-y[i4]))
print(min(ans))
### BUGGY CODE ###

N,M=map(int,input().split())
S=input()
T=input()
list_S=list(S)
list_T=list(T)
Number_i=[i for i in range(N)]
Number_j=[j for j in range(M)]
Kaburi_i=[]
Kaburi_j=[]
counter=0
Flag=0
for i in Number_i:
  if i*M/N in Number_j:
    Kaburi_i.append(i)
    Kaburi_j.append(int(i*M/N))
Kaburi_Size=len(Kaburi_i)
while counter<=Kaburi_Size-1:
  if list_S[Kaburi_i[counter]]==list_T[Kaburi_j[counter]]:
    pass
  else:
    Flag=1
    break
  counter+=1
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a
if Flag==1:
  print(-1)
else:
  print(int(N*M/gcd(N,M)))
  
  
  





### FIXED CODE ###

N,M=map(int,input().split())
S=input()
T=input()
list_S=list(S)
list_T=list(T)
Number_i=[i for i in range(N)]
Number_iMN=[]
for i in Number_i:
  Number_iMN.append(i*M/N)
Number_j=[j for j in range(M)]
Kaburi_j=list(set(Number_iMN)&set(Number_j))
Kaburi_i=[]
for j in Kaburi_j:
  Kaburi_i.append(int(j*N/M))
counter=0
Flag=0
Kaburi_Size=len(Kaburi_i)
while counter<=Kaburi_Size-1:
  if list_S[int(Kaburi_i[counter])]==list_T[int(Kaburi_j[counter])]:
    pass
  else:
    Flag=1
    break
  counter+=1
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a
if Flag==1:
  print(-1)
else:
  print(int(N*M/gcd(N,M)))
### BUGGY CODE ###

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


ans = 0
while True :
    if C > 0 :
        C -= 1
        ans += 1
        if B > 0 :
            B -= 1
            ans += 1
        elif A > 0 :
            A -= 1
        else :
            break
    elif B > 0 :
        B -= 1
        ans += 1
        if A > 0 :
            A -= 1
        else :
            break
    else :
        break
        
print(ans)

### FIXED CODE ###

A,B,C = map(int,input().split())
ans = 0
if (A+B) >= C :
    ans += B+C
else :
    ans += min(B,C)*2
    ans += min(A,C)
    ans += 1
print(ans)
### BUGGY CODE ###

MOD = 10**9+7
k = int(input())
s = input()
n = len(s)


def com(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
    Y = pow(Y, MOD-2, MOD)
    return X*Y % MOD


ans = 0
for x in range(k+1):
    ans += pow(26, x, MOD)*com(n+k-x-1, n-1)*pow(25, k-x, MOD)
print(ans % MOD)


### FIXED CODE ###

MOD = 10**9+7
k = int(input())
s = input()
n = len(s)


U = n+k
fact = [0]*(U+1)
fact[0] = 1
for i in range(1, U+1):
    fact[i] = fact[i-1]*i % MOD


invfact = [0]*(U+1)
invfact[U] = pow(fact[U], MOD-2, MOD)
for i in reversed(range(U)):
    invfact[i] = invfact[i+1]*(i+1) % MOD


def nCr(n, r):
    if r < 0 or n < r:
        return 0
    return fact[n]*invfact[r]*invfact[n-r]


ans = 0
for x in range(k+1):
    ans += pow(26, x, MOD)*nCr(n+k-x-1, n-1)*pow(25, k-x, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
tl = [list() for _ in range(n)]
ab = [None] * (n-1)
ans = [0] * n

for i in range(n-1):
    ab[i] = tuple(map(int, input().split()))

ab.sort(reverse=True)

for a, b in ab:
    a -= 1
    b -= 1
    tl[a].append(b)
    tl[a].extend(tl[b])

for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x
    for num in tl[p-1]:
        ans[num] += x

print(" ".join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
 
n, q = map(int, input().split())
tl = [list() for _ in range(n)]
xl = [0] * n
ans = [0] * n
 
for i in range(n-1):
    a, b = map(int, input().split())
    tl[a-1].append(b-1)
    tl[b-1].append(a-1)
 
for i in range(q):
    p, x = map(int, input().split())
    xl[p-1] += x

def rec(p, parent, x):
    x += xl[p]
    ans[p] = x
    for num in tl[p]:
        if num == parent: continue
        rec(num, p, x)

rec(0, -1, 0)
 
print(*ans)
### BUGGY CODE ###

N = int(input())
L = sorted(map(int, input().split()))

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[k] - L[i] < L[j] < L[i] + L[k]:
                ans += 1
print(ans)


### FIXED CODE ###

import bisect

N = int(input())
L = sorted(map(int, input().split()))

ans = 0
for a in range(N):
    for b in range(a+1, N):
        ab = L[a] + L[b]
        left = b + 1
        right = bisect.bisect_left(L, ab)
        ans += right - left

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

from collections import defaultdict
N,M=list(map(int, input().strip().split()))
A=list(map(int, input().strip().split()))
AS=[0]*N
AS[0]=A[0]%M
modG=defaultdict(list)
ct=0
for i in range(1,N):
    AS[i]=(AS[i-1]+A[i])%M
for i,a in enumerate(AS):
    if a==0:ct+=1
    modG[a].append(i)
for i in range(N):
    for x in modG[AS[i]]:
        if x+1>i:break
        ct+=1
print(ct)

### FIXED CODE ###

from collections import defaultdict
def binsearch_int(func, min_x, max_x):
    """func(x) == Trueとなる最大のxを返す
    """
    if func(max_x):
        return max_x
    if not func(min_x):
        return None
    left,right=min_x,max_x
    while left+1<right:
        mid=(left+right)//2
        if func(mid):
            left=mid
        else:
            right=mid
    return left
N,M=list(map(int, input().strip().split()))
A=list(map(int, input().strip().split()))
AS=[0]*N
AS[0]=A[0]%M
modG=defaultdict(list)
ct=0
for i in range(1,N):
    AS[i]=(AS[i-1]+A[i])%M
for i,a in enumerate(AS):
    if a==0:ct+=1
    modG[a].append(i)
for i in range(N):
    ans=binsearch_int(lambda x: modG[AS[i]][x]+1<=i,0,len(modG[AS[i]])-1)
    if ans is None:
        continue
    ct+=(ans+1)
print(ct)
### BUGGY CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]

dp=[[0]*(w+1) for _ in range(n+1)]
#dpテーブル

def rec(i,j):#再帰　i:何個目の商品を見てるか　j:残りのナップサックの容量
    if dp[i][j] != 0:#メモされてればそれを返す
        return dp[i][j]
    res = 0
    if i == n:#すべての商品を調べ終えた
        return res
    else:
        if j - l[i][0] < 0:#容量が足りない
            ans = rec(i+1,j)
        else:
            #品物を入れるときと入れないとき両方調べる
            ans = max(rec(i+1,j),rec(i+1,j-l[i][0]) + l[i][1])
    dp[i][j] = ans#メモして返す
    return dp[i][j]

print(rec(0,w))

### FIXED CODE ###

n,w=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(n)]

dp=[[0]*(w+1) for _ in range(n+1)]
#dp:=i番目以降の商品から重さの総和がj以下となるように選んだ時の価値の総和の最大

#初期条件 dpｗｐ0で作ってるのでいらない
for j in range(w):dp[n][j] = 0

#漸化式
#dp[i][j] = dp[i+1][j] (j < w[i])
#           max(dp[i+1][j] , dp[i+1][j-w[i]]+v[i]) (otherwise)
for i in reversed(range(n)):
    for  j in range(w+1):
        if j < l[i][0]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j] , dp[i+1][j - l[i][0]] + l[i][1] )

print(dp[0][w])
### BUGGY CODE ###


from heapq import heappush, heappop
 
 
class Dijk:
    def __init__(self, n):
        self.table = [[] for i in range(n+1)]
        self.n = n+1
 
    def add(self, x, y, f):
        self.table[x].append((y, f))
 
    def di(self, s):
        inf = float('inf')
        self.val = [inf] * self.n
        self.val[s] = 0
        h = []
        heappush(h, (0, s))
        while h:
            q, i = heappop(h)
            if self.val[i] < q:
                continue
            for x, c in self.table[i]:
                if self.val[x] > self.val[i] + c:
                    self.val[x] = self.val[i] + c
                    heappush(h, (self.val[x], x))
 
    def dist(self, s, t):
        return self.val[t]

n= int(input())
dijk=Dijk(n)

for i in range(n-1):
    a,b,c=map(int,input().split())
    dijk.add(a,b,c)
    dijk.add(b,a,c)
q,k=map(int,input().split())
for i in range(q):
    x,y=map(int,input().split())
    dijk.di(x)
    ans=dijk.dist(x,k)
    dijk.di(k)
    ans+=dijk.dist(k,y)
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


n=int(input())
graph=[[] for i in range(n+1)]
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))
    
q,k=map(int,input().split())

dis=[None]*(n+1)

def set_dis(x,d):
    dis[x]=d
    for yy,dd in graph[x] :
        if dis[yy] is not None:
            continue
        set_dis(yy,dd+d)
set_dis(k,0)

for i in range(q):
    x,y=map(int,input().split())
    print(dis[x]+dis[y])
### BUGGY CODE ###

import sys
import copy
import itertools
input = sys.stdin.readline

N=int(input())

A=[]
for i in range(100):
    A.append(i+1)

D=list(itertools.combinations_with_replacement(A, 3))
#print(D)
for j in range(N):
    count=0
    for sa in D:
        if ((sa[0]+sa[1]+sa[2])**2)-(sa[0]*sa[1]+sa[1]*sa[2]+sa[2]*sa[0])==j+1:
            if sa[0]!=sa[1] and sa[1] !=sa[2]:
                
                count+=6
            elif sa[0]==sa[1] and sa[1]==sa[2]:
                count+=1
            else:
                count+=3

    print(count)


### FIXED CODE ###

import sys

import itertools
input = sys.stdin.readline
 
N=int(input())

ans=[0]*10050

for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            v=i*i+j*j+k*k+i*j+i*k+j*k
            if v<10050:
                ans[v]+=1

for i in range(N):
    print(ans[i+1])
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    query = input()
    if query[0] == "1":
        S = S[::-1]
    else:
        _,F,C = query.split()
        if F == "1":
            S = C + S
        else:
            S = S + C
print(S)



### FIXED CODE ###

from collections import deque

S = deque(input())
Q = int(input())
flg = True
for _ in range(Q):
    query = input()
    if query[0] == "1":
        flg = not flg
    else:
        _,F,C = query.split()
        if (F == "1" and flg) or (F == "2" and not flg):
            S.appendleft(C)
        else:
            S.append(C)
if not flg:
    S.reverse()

print(''.join(S))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
print(sum(A[i] * A[j] for i in range(N) for j in range(i+1, N)) % (1_000_000_007))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
tmp = sum(A)
sum_ = 0

for a in A:
    tmp -= a
    sum_ += a * tmp

print(sum_ % (1_000_000_007))
### BUGGY CODE ###

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

a=[]#種類の記憶
for i in range(n):
  if a.count(lst[i]) == 0:
    a.append(lst[i])
c=[]#カウント用
for j in a:
  c.append(lst.count(j))
ans = 0
while k < len(a):
  i = c.index(min(c)) #最小の個数のインデックス
  ans += min(c)
  del a[i]
  del c[i]
print(ans)

### FIXED CODE ###

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

num = []
cnt = []

for i in range(N):
    if i == 0:
        num.append(A[i])
        cnt.append(1)
    else:
        if A[i-1] != A[i]:
            num.append(A[i])
            cnt.append(1)
        else:
            cnt[-1] += 1
cnt.sort()
#print(num,cnt)

res = 0
M = len(cnt)
if M <= K:
    res = 0
else:
    for i in range(M-K):
        res += cnt[i]
print(res)
### BUGGY CODE ###

import bisect

n = int(input())


a, b = map(int, input().split())
task_lis = [[b, a]]

k = 1

for i in range(n-1):
    a, b = map(int, input().split())
    ok2 = bisect.insort_right(task_lis,[b, a])

sum_a = 0

ch_over = 1
for i in range(n):
    sum_a += task_lis[i][1]
    if task_lis[i][0] < sum_a:
        ch_over = 0
        break

if ch_over == 0:
    print("No")
else:
    print("Yes")


### FIXED CODE ###

n = int(input())
task_lis = sorted([[int(i) for i in input().split()] for _ in range(n)], key = lambda x:x[1])


sum_a = 0
ch_over = 1

for i in range(n):
    sum_a += task_lis[i][0]
    if task_lis[i][1] < sum_a:
        ch_over = 0
        break

if ch_over == 0:
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

from bisect import bisect

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [0] * n
for i, p in enumerate(ppp, start=1):
    qqq[p - 1] = i

dp = [(0, 0)]
for i in qqq:
    s = bisect(dp, (i,))
    ndp = [(j, cost + b) for j, cost in dp[:s]]
    stay_cost = dp[s - 1][1]
    ndp.append((i, stay_cost))
    ndp.extend((j, cost + a) for j, cost in dp[s:] if stay_cost > cost + a)
    dp = ndp
print(dp[-1][1])


### FIXED CODE ###

from bisect import bisect
from operator import itemgetter

n, a, b = map(int, input().split())
ppp = map(int, input().split())
qqq = [i for i, p in sorted(enumerate(ppp, start=1), key=itemgetter(1))]
INF = 10 ** 15

dp = [(0, 0)]
for i in qqq:
    ndp = []
    s = bisect(dp, (i,))
    tmp_min = INF
    for j, cost in dp[:s]:
        cost += b
        ndp.append((j, cost))
        tmp_min = cost
    stay_cost = dp[s - 1][1]
    if tmp_min > stay_cost:
        ndp.append((i, stay_cost))
        tmp_min = stay_cost
    for j, cost in dp[s:]:
        cost += a
        if tmp_min > cost:
            ndp.append((j, cost))
            tmp_min = cost
    dp = ndp

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

S = input()
Q = int(input())
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    if F == '1':
      S = C+S
    else:
      S = S+C
  else:
    T = Query
    S = S[::-1]
print(S)

### FIXED CODE ###

S = input()
Q = int(input())
flip = 0
head = []
tail = []
for i in range(Q):
  Query = input().split()
  if len(Query) == 3:
    T,F,C = Query
    F = int(F)-1
    if F^flip == 1:
      tail.append(C)
    else:
      head.append(C)
  else:
    flip ^= 1
if flip:
  head, tail = tail, head
  S = S[::-1]
head = ''.join(head[::-1])
tail = ''.join(tail)
print(head+S+tail)
### BUGGY CODE ###

N = int(input()) 
sub = list(map(int,input().split())) 
number = list(range(1, N+1, 1)) 
cnt = 0 
for i in range(N):
    for j in range(int(len(sub))):
        if number[i] == sub[j]:
            cnt = cnt + 1
        
    print(cnt)
    cnt = 0

### FIXED CODE ###

N = int(input())
sub = list(map(int, input().split()))
ans = [0]*(N)
for i in sub:
    ans[i-1] += 1
for i in ans:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

#input
N = int(input())
A = list(map(int, input().split()))
 
#output
from collections import Counter
from operator import itemgetter
l = Counter(A).most_common()
 
maximum_operation = [0] * N
for K in range(len(l)):
    l = Counter(A).most_common()
    while l[K][1] > 0:
        for i in range(K+1):
            l[i] = (l[i][0], l[i][1]-1)
        l.sort(key=itemgetter(1), reverse = True)
        maximum_operation[K] += 1
 
for m in maximum_operation:
    print(m)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

def main():
    s = input()
    mod = 2019

    s2 = ''
    R = [0] * mod
    R[0] += 1
    for i in range(len(s)):
        s2 = f'{s[-i - 1]}{s2}'
        R[int(s2) % mod] += 1

    print(sum([r * (r - 1) // 2 for r in R]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    s = input()
    mod = 2019

    n = 0
    R = [0] * mod
    R[0] += 1
    for i in range(len(s)):
        n += int(s[-i - 1]) * pow(10, i, mod)
        R[n % mod] += 1

    print(sum([r * (r - 1) // 2 for r in R]))


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

inp = [input() for i in range(2)]
N = int(inp[0])
A = list(map(int, inp[1].split()))
B = 0
for k in A:
    a = A.count(k)
    B += (a - 1) / 2

for k in range(N):
    c = A.count(A[k]) - 1
    counter = B - c
    print(int(counter))


### FIXED CODE ###

import math
inp = [input() for i in range(2)]
N = int(inp[0])
A = list(map(int, inp[1].split()))
# B = 0
d = {}
for k in A:
    # a = A.count(k)
    # B += (a - 1) / 2
    if k in d.keys():
        d[k] += 1
    else:
        d[k] = 1

# for k in range(N):
#     c = A.count(A[k]) - 1
#     counter = B - c
#     print(int(counter))

p = {}
for k in d.keys():
    cnt = d[k]
    p[k] = cnt * (cnt-1) / 2

total = sum(p.values())

for item in A:
    print(int(total - d[item] + 1))
### BUGGY CODE ###

n = int(input())
A=list(map(int,input().split()))
cnt=0
for i in range(n):
    D=min(A[j] for j in range(i+1))
    #print(D)
    if A[i]<=D:
        cnt+=1
    else:
        pass
print(cnt)


### FIXED CODE ###

n = int(input())
A=list(map(int,input().split()))
cnt=0
tmp=n+1
for i in range(n):
    if A[i]<=tmp:
        tmp=A[i]
        cnt+=1
    else:
        pass
print(cnt)
### BUGGY CODE ###

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

r_num = S.count("R")
g_num = S.count("G")
b_num = S.count("B")

count = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j * 2 - i
        if k >= N:
            continue
        si, sj, sk = S[i], S[j], S[k]
        if si != sj and sj != sk and sk != si:
            count += 1

print(r_num * g_num * b_num - count)

### FIXED CODE ###

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

r_num = S.count("R")
g_num = S.count("G")
b_num = S.count("B")

count = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        k = j * 2 - i
        if k >= N:
            continue
        si, sj, sk = S[i], S[j], S[k]
        if si != sj and sj != sk and sk != si:
            count += 1

print(r_num * g_num * b_num - count)