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

from heapq import *

n = int(input())
nn = 2 ** n
aa = list(map(int, input().split()))
hp = []
ans = [-1] * nn
for i in range(nn-1):
    for j in range(i+1,nn):
        heappush(hp, [-(aa[i]+aa[j]), i|j])
r=nn
i=2
while i>1:
    s, i = heappop(hp)
    if ans[i]==-1:
        for ii in range(i,r):
            ans[ii]=-s
        r=i
for x in ans[1:]:
    print(x)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Top2:
    def __init__(self,x=-1,y=-1):
        if x<y:x,y=y,x
        self.val=[x,y]
        self.s=x+y

    def __add__(self, other):
        i=j=0
        self.val=sorted(self.val+other.val,reverse=True)[:2]
        self.s=sum(self.val)
        return self

n=II()
aa=LI()
dp=[Top2(a) for a in aa]

for i in range(n):
    for j in range((1<<n)-1,-1,-1):
        if j>>i&1:continue
        dp[j|1<<i]+=dp[j]

mx=-1
for j in range(1,1<<n):
    mx=max(mx,int(dp[j].s))
    print(mx)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)

class Solver(object):
    def __init__(self,N:int,W:int,values:list,weights:list):
        self.N = N   ## MAX number of item
        self.values = values  ## list of item value
        self.weights = weights ## list of item weight
        self.dp = [[None for _ in range(W+1)] for _ in range(N+1)] ## memorize the result

    ## i番目以降から重さがj以下になるように選ぶ時に価値が最大になるようにする。
    def solve(self,i:int,j:int) -> int:
        if self.dp[i][j] != None:
            return self.dp[i][j]
        if i == self.N:
            res = 0
        elif j < self.weights[i]:
            res = self.solve(i+1,j)
        else:
            res = max(self.solve(i+1,j),self.solve(i+1,j-self.weights[i])+self.values[i])
        self.dp[i][j] = res
        return res

def main():
    N,W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    weights = [item[0] for item in items]
    values = [item[1] for item in items]
    solver = Solver(N,W,values,weights)
    ans = solver.solve(0,W)
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


def main():
    N, W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, W, items)
    print(solver.solve())


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

S = input()
mod = 10 ** 9 + 7

ret = 0
la, rc = 0, S.count('C')
lq, rq = 0, S.count('?')

fac = [1]
inv = [1]
for i in range(1, len(S) + 1) :
    fac.append(fac[-1] * i % mod)
    inv.append(pow(fac[-1], mod - 2, mod))

def comb(ac, q) :
    ret = 0
    for i in range(q + 1) :
        ret += pow(2, q - i, mod) * (ac + i) * fac[q] * inv[q-i] * inv[i] % mod
        
    return ret

for s in S :
    if s == '?' :
        rq -= 1
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
        lq += 1
    elif s == 'A' :
        la += 1
    elif s == 'B' :
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
    elif s == 'C' :
        rc -= 1
    
print(ret)

### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7

ret = 0
la, rc = 0, S.count('C')
lq, rq = 0, S.count('?')

def comb(ac, q) :
    if q == 0 :
        return ac * pow(3, q, mod) % mod
    else :
        p = pow(3, q - 1, mod)
        return (q * p + ac * p * 3) % mod

for s in S :
    if s == '?' :
        rq -= 1
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
        lq += 1
    elif s == 'A' :
        la += 1
    elif s == 'B' :
        ret += comb(la, lq) * comb(rc, rq)
        ret %= mod
    elif s == 'C' :
        rc -= 1
    
print(ret)
### BUGGY CODE ###

MOD = 10**9 + 7

s = input().strip()
ss = s[::-1]
rs = [10**i % 13 for i in range(6)]

n = len(s)
dp = [[0] * 13 for _ in range(n)]
for i, c in enumerate(ss):
    if i == 0:
        if c == '?':
            for j in range(10):
                dp[i][j] = 1
        else:
            dp[i][int(c)] = 1
    else:
        r = rs[i % 6]
        if c == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][(j + r * k) % 13] += dp[i - 1][j]
        else:
            for j in range(13):
                dp[i][(j + r * int(c)) % 13] += dp[i - 1][j]
        for j in range(13):
            dp[i][j] %= MOD
print(dp[n - 1][5] % MOD)

### FIXED CODE ###

MOD = 10**9 + 7

s = input().strip()
ss = s[::-1]
rs = [10**i % 13 for i in range(6)]

n = len(s)
dp = [[0] * 13 for _ in range(n)]
for i, c in enumerate(ss):
    if i == 0:
        if c == '?':
            for j in range(10):
                dp[i][j] = 1
        else:
            dp[i][int(c)] = 1
    else:
        r = rs[i % 6]
        if c == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][(j + r * k) % 13] += dp[i - 1][j]
        else:
            for j in range(13):
                dp[i][(j + r * int(c)) % 13] += dp[i - 1][j]
        for j in range(13):
            dp[i][j] %= MOD
print(dp[n - 1][5] % MOD)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
for i in range(m):
  a[0]=a[0]/2
  for j in range(1,n):
    if a[0]>a[j]:
      a.insert(j,a[0])
      del a[0]
      break
import math
ans=0
for i in range(n):
  ans=ans+math.floor(a[i])
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=a[i]*-1
import heapq
heapq.heapify(a)
for i in range(m):
  t=(heapq.heappop(a))*-1
  heapq.heappush(a,(t//2)*-1)
print(sum(a)*-1)
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    for j in range(i+1, N+1):
        if sum(A[i:j]) % M == 0:
            ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
N, M = (list)(map(int, input().split()))
A = (list)(map(int, input().split()))
A[0] %= M

for i in range(1, N):
    A[i] += A[i-1]
    A[i] %= M

ans = 0

C = Counter(A)
for num, val in C.items():
    if num == 0:
        ans += val
    if val >= 2:
        ans += val*(val-1)//2
print(ans)
### BUGGY CODE ###

a, b, n = map(int, input().split())
if b > n:
    ans = (a*n)//b
else:
    ans = 0
    for i in range(n//b +1):
        result = a*(b*(i+1)-1)//b - a*i
        if result > ans:
          ans = result
        
print(ans)

### FIXED CODE ###

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

print(int(a*min(n,b-1)/b))
### BUGGY CODE ###

K = int(input())
def gcd(a,b,c):
    if min(a,b,c) == 1:
        return 1

    arr = []
    for i in range(2, min(a,b,c)+1):
        if a%i == b%i == c%i == 0:
            cnt = 0
            while a%i == b%i == c%i == 0:
                cnt += 1
                a //= i
                b //= i
                c //= i
            arr.append([i, cnt])

    if a==b==c and a!=1:
        arr.append([a, 1])

    ans = 1
    for i in range(len(arr)):
        ans *= arr[i][0]**arr[i][1]
    return ans

Ans = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            if i==j==k:
                Ans+=gcd(i,j,k)
            elif len({i,j,k}) == 2:
                Ans+=gcd(i,j,k)*3
            else:
                Ans+=gcd(i,j,k)*6
print(Ans)

### FIXED CODE ###

from math import gcd
K = int(input())
ans = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        temp = gcd(i,j)
        for k in range(j,K+1):
            if i==j==k:
                ans+=gcd(temp, k)
            elif len({i,j,k}) == 2:
                ans+=gcd(temp, k)*3
            else:
                ans+=gcd(temp, k)*6
print(ans)
### BUGGY CODE ###

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

for i in range(1,n+1):
    num=a.count(i)
    print(num)

### FIXED CODE ###

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

cnt=[0]*(n+1)
for i in range(n-1):
    cnt[a[i]]+=1

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

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

import collections

buk = [0] * (10**5 + 1)
for e in a:
  buk[e] += 1


# dprint(buk)

for b, c in bc:
  sum = 0
  for k in range(10 ** 5 + 1):
    if buk[k] == 0:
      continue
    if k == b:
      # dprint(b, c)
      buk[c] += buk[b]
      buk[b] = 0
      # dprint(buk)
      sum += c * buk[c]
    else:
      if k != c:
        sum += k * buk[k]
    # dprint('sum', '=', sum)
  print(sum)


### FIXED CODE ###

import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

import collections

buk = [0] * (10**5 + 1)
for e in a:
  buk[e] += 1

s = sum(a)

for b, c in bc:
  s += (c - b) * buk[b]
  buk[c] += buk[b]
  buk[b] = 0
  print(s)
### BUGGY CODE ###

from collections import Counter

MOD = 10**9 + 7

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

ptns = Counter([(0, 0, 0)])
#print('ptns:', ptns)
for A in As:
    ptn2s = Counter()
    for ptn, num in ptns.items():
        for i in range(3):
            if ptn[i] == A:
                ptn2 = list(ptn)
                ptn2[i] += 1
                ptn2s[tuple(ptn2)] += num
                ptn2s[tuple(ptn2)] %= MOD
    ptns = ptn2s

#print(ptns)
print(sum(ptns.values()) % MOD)


### FIXED CODE ###

from collections import Counter

MOD = 10**9 + 7

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

ptns = Counter([(0, 0, 0)])
#print('ptns:', ptns)
for A in As:
    ptn2s = Counter()
    for ptn, num in ptns.items():
        for i in range(3):
            if ptn[i] == A:
                ptn2 = list(ptn)
                ptn2[i] += 1
                ptn2s[tuple(ptn2)] += num
                ptn2s[tuple(ptn2)] %= MOD
    ptns = ptn2s

#print(ptns)
print(sum(ptns.values()) % MOD)
### BUGGY CODE ###

import copy
import math
import collections

inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_dict = {}
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    if 2 not in prime_dict.keys():
        prime_dict[2] = 1
    else:
        prime_dict[2] += 1
for i in range(3, int(math.sqrt(m)) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        if i not in prime_dict.keys():
            prime_dict[i] = 1
        else:
            prime_dict[i] += 1
if m_copy != 1:
    if m_copy not in prime_dict.keys():
        prime_dict[m_copy] = 1
    else:
        prime_dict[m_copy] += 1
b = list(prime_dict.values())
ans = 1
for bb in b:
    ans *= math.factorial(bb + n - 1) % inf
    ans *= pow(math.factorial(bb), inf - 2, inf)
    ans *= pow(math.factorial(n - 1), inf - 2, inf)
    ans = ans % inf
print(ans)

### FIXED CODE ###

import copy
import math
import collections

inf = (10 ** 9) + 7
n, m = map(int, input().split())
prime_dict = {}
m_copy = copy.deepcopy(m)
while (m_copy % 2 == 0):
    m_copy = int(m_copy // 2)
    if 2 not in prime_dict.keys():
        prime_dict[2] = 1
    else:
        prime_dict[2] += 1
for i in range(3, int(math.sqrt(m)) + 1, 2):
    while (m_copy % i == 0):
        m_copy = int(m_copy // i)
        if i not in prime_dict.keys():
            prime_dict[i] = 1
        else:
            prime_dict[i] += 1
if m_copy != 1:
    if m_copy not in prime_dict.keys():
        prime_dict[m_copy] = 1
    else:
        prime_dict[m_copy] += 1
b = list(prime_dict.values())
ans = 1

dp = [[1 for _ in range(30)] for _ in range(n)]
for i in range(1, 30):
    for j in range(1,n):
        dp[j][i] = (dp[j - 1][i] + dp[j][i - 1]) % inf

for bb in b:
    ans *= dp[n - 1][bb]
    ans = ans % inf
print(ans)
### BUGGY CODE ###

from collections import Counter
n=int(input())
l=[list(str(input())) for i in range(n)]
nums=[x for x in range(n-1)]
cnt=0
for i in nums:
  for j in l[i+1:]:
    if(Counter(l[i])==Counter(j)):
      cnt+=1
print(cnt)

### FIXED CODE ###

from collections import Counter
n=int(input())
l=["".join(sorted(list(str(input())))) for i in range(n)]
cnt=Counter(l)
ans=0
for i in set(l):
  n=cnt[i]
  ans+=n*(n-1)//2
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
data=[[int(x) for x in input().split()] for m in range(M)]
_min=min([m[0] for m in data])
_max=max([m[1] for m in data])
data=[list(range(m[0],m[1]+1)) for m in data]
#print(data)
count=0
for i in range(_min,_max+1):
    count+=(sum([(i in m) for m in data])==len(data))
print(count)


### FIXED CODE ###

N,M=map(int,input().split())
data=[[int(x) for x in input().split()] for m in range(M)]
_min=max([m[0] for m in data])
_max=min([m[1] for m in data])
a=_max-_min+1
print(a if a>=0 else 0)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
import itertools
import heapq


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 10 ** 9 + 7
    A.sort()
    A = deque(A)
    #    print(A)
    A_minus = deque([s for s in A if s < 0])
    A_plus = deque([s for s in A if s >= 0])

    #    print(A_plus)
    #    print(A_minus)
    AA = []
    if N == K:
        ans = 1
        for i in A:
            ans *= i % mod
        print(ans % mod)

    elif K % 2 == 0:
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)
        ans = 1
        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
        print(ans % mod)

    elif len(A_plus) == 0:
        ans = 1
        for i in range(K):
            ans *= A_minus.pop() % mod
        print(ans % mod)

    else:
        ans = A_plus.pop()
        while len(A_minus) >= 2:
            a1 = A_minus.popleft()
            a2 = A_minus.popleft()
            AA.append(-a1 * a2)

        while len(A_plus) >= 2:
            a1 = A_plus.pop()
            a2 = A_plus.pop()
            AA.append(-a1 * a2)

        heapq.heapify(AA)
        for i in range(K // 2):
            ans *= (-1 * heapq.heappop(AA)) % mod
        print(ans % mod)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

# import bisect
# import numpy as np
# from collections import deque
from collections import deque
# map(int, sys.stdin.read().split())
# import heapq
import bisect


# def input():
#     return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    mod = 10 ** 9 + 7

    if N == K:
        ans = 1
        for i in range(N):
            ans *= A[i]
            ans %= mod
        print(ans % mod)



    elif K % 2 == 0:
        ans = 1
        j = 0
        i = N - 1
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)

    elif A[-1] < 0:
        ans = 1
        for i in range(K):
            ans *= A[-(i + 1)]
            ans %= mod
        print(ans % mod)
    else:
        ans = A[-1]
        j = 0
        i = N - 2
        for _ in range(K // 2):
            if A[j] * A[j + 1] > A[i] * A[i - 1]:
                ans *= A[j] * A[j + 1]
                ans %= mod
                j += 2
            else:
                ans *= A[i] * A[i - 1]
                ans %= mod
                i -= 2
        print(ans % mod)


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

N, Q = map(int,input().split())
S = list(input())
lr = [list(map(int,input().split())) for i in range(Q)]
ans = ''
skip = 0
for i in range(N-1):
  if skip == 0:
    if S[i] + S[i+1] == 'AC':
      ans += '12'
      skip = 1
    else:
      ans += '0'
  else:
    skip = 0
  
  if i == N - 2:
    ans += '0'
else:
  for i in range(Q):
    l = lr[i][0]
    r = lr[i][1]
    string = ans[l-1:r]
    print(string.count('12'))

### FIXED CODE ###

N, Q = map(int,input().split())
S = list(input())
lr = [list(map(int,input().split())) for i in range(Q)]
ans = ''
a = [0]
count = 0
for i in range(N-1):
  if S[i] + S[i+1] == 'AC':
    ans += '1'
  else:
    ans += '0'
  if i == N - 2:
    ans += '0'
else:
  for i in range(N):
    if ans[i] == '1':
      count += 1
      a.append(count)
    else:
      a.append(count)
  else:
    for i in range(Q):
      l = lr[i][0]
      r = lr[i][1]
      print(a[r-1]-a[l-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for x in range(N):
    A[x] -= (x+1)

sorted_A = sorted(A)

if len(A) == 1:
    ans = 0
elif N % 2 == 1 and not len(A) == 1 :
    ans = sum(map(lambda x: abs(x-sorted_A[N//2+2]),A))
    for x in range(sorted_A[N//2],sorted_A[N//2+2]):
        y = sum(map(lambda z: abs(z -x),A))
        if ans > y :
            ans = y
else:
    ans = sum(map(lambda x: abs(x-sorted_A[N//2+1]),A))
    for x in range(sorted_A[N//2],sorted_A[N//2+1]):
        y = sum(map(lambda z: abs(z -x),A))
        if ans > y :
            ans = y
    
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
for x in range(N):
    A[x] -= (x+1)

sorted_A = sorted(A)

if len(A) == 1:
    ans = 0
else:
    ans = sum(map(lambda x: abs(x-sorted_A[N//2]),A))

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

n = int(input())
a = [int(input()) for _ in range(n)]
L = []
cnt = 0
i = 0
while True:
    if i in L:
        print(-1)
        break
    else:
        L.append(i)
        i = a[i] - 1
        cnt += 1
        if i == 1:
            print(cnt)
            break


### FIXED CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]
L = [0] * n
cnt = 0
i = 0
while True:
    if L[i] == 1:
        print(-1)
        break
    else:
        L[i] = 1
        i = a[i] - 1
        cnt += 1
        if i == 1:
            print(cnt)
            break
### BUGGY CODE ###

n,y = map(int,input().split())
for a in range(n+1):
  for b in range(n+1):
    for c in range(n+1):
      if 10000*a + 5000*b + 1000*c == y and a+b+c == n:
        print(a,b,c)
        exit()
print("-1 -1 -1")

### FIXED CODE ###

n,y = map(int,input().split())
for a in range(n+1):
  for b in range(n+1):
    c = n-a-b
    if 10000*a + 5000*b + 1000*c == y and a+b+c == n and c >= 0:
      print(a,b,c)
      exit()
print("-1 -1 -1")
### BUGGY CODE ###

S = input()
ans = [0 for i in range(len(S))]
for i in range(len(S)):
    odd = True
    j = i
    odd_j = i
    init_S = S[j]
    while init_S == S[j]:
        if S[j] == 'R':
            j += 1
        else:
            j -= 1
        odd = not odd
        if odd:
            odd_j = j
    ans[odd_j] += 1

print(*ans)

### FIXED CODE ###

S = input()
ans = [0 for i in range(len(S))]

odd = 0
even = 0
for i in range(len(S)):
    if S[i] == 'R':
        tmp = even
        even = odd + 1
        odd = tmp
    else:
        ans[i-1] += even
        ans[i] += odd
        odd = 0
        even = 0

for i in range(len(S)):
    if S[-i-1] == 'L':
        tmp = even
        even = odd + 1
        odd = tmp
    else:
        ans[-i] += even
        ans[-i-1] += odd
        odd = 0
        even = 0

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

def main():

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

    s = set()
    for i in range(M):
        a, b = map(int ,input().split())
        temp = list(map(int, input().split()))
        for j in range(b): s.add(temp[j])
        A.append([a, temp])

    if(len(s) < N): return -1

    cur = dict()
    cur[0] = 0
    for i in range(M):
        temp = cur.copy()
        for v in temp:
            cost = A[i][0]
            u = v
            for j in A[i][1]:
                u |= 1 << j
            if u in cur: cur[u] = min(cur[u], cur[v] + cost)
            else: cur[u] = cur[v] + cost

    target = 0
    for i in range(1, N+1): target |= 1 << i
    return cur[target]


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():

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

    s = set()
    d = dict()
    for i in range(M):
        a, b = map(int ,input().split())
        temp = list(map(int, input().split()))
        v = 0
        for j in range(b):
            s.add(temp[j])
            v |= 1 << temp[j]
        if v in d: d[v] = min(d[v], a)
        else: d[v] = a

    if(len(s) < N): return -1

    M = len(d)
    cur = dict()
    cur[0] = 0
    for g in d:
        temp = cur.copy()
        for v in temp:
            cost = d[g]
            u = v | g
            if u in cur: cur[u] = min(cur[u], cur[v] + cost)
            else: cur[u] = cur[v] + cost

    target = 0
    for i in range(1, N+1): target |= 1 << i
    return cur[target]


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

n,m=map(int,input().split())
a=[int(i) for i in input().split()]

ans=0

for r in range(n):
    for l in range(r+1):
        if sum(a[l:r+1])%m==0:
            ans+=1

print(ans)

### FIXED CODE ###

import collections

n,m=map(int,input().split())
a=[int(i) for i in input().split()]

s=0
ans=0
l=[]

for i in a:
    s+=i
    l.append(s%m)

c=collections.Counter(l)

for p,q in c.items():
    if int(p)==0:
        ans+=q*(q+1)//2
    else:
        ans+=q*(q-1)//2


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

import re

def main():
    NumString = int(input())
    String = input()
    
    total_ans = 0
    for i, i_string in enumerate(String[:-2]):
        RGB = 'RGB'
        for j, j_string in enumerate(String[i+1:-1], i+1):
            if i_string == j_string:
                continue

            k_RGB = RGB.replace(i_string, '').replace(j_string, '')
            total_ans += String.count(k_RGB, j+1)
            if (j + (j-i)) < NumString and String[j + (j-i)] == k_RGB:
                total_ans -= 1
    
    print(total_ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

NumString = int(input())
String = input()

r_string_num, g_string_num, b_string_num = 0, 0, 0
for i_string in String:
    if i_string == 'R':
        r_string_num += 1
    elif i_string == 'G':
        g_string_num += 1
    else:
        b_string_num += 1
    
total_ans = r_string_num * g_string_num * b_string_num

exclude_num = 0
for i in range(NumString-2):
    for j in range(i+1, NumString-1):
        if (2*j - i) < NumString and String[i] != String[j] and \
            String[j] != String[2*j-i] and String[i] != String[2*j-i]:
            exclude_num += 1

total_ans -= exclude_num

print(total_ans)