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

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

r=[]
g=[]
b=[]

for i in range(n):
    if s[i]=="R":
        r.append(i+1)
    elif s[i]=="G":
        g.append(i+1)
    else:
        b.append(i+1)

lenr=len(r)
leng=len(g)
lenb=len(b)

isum=0
for ir in r:
    for ig in g:
        if (ir+ig)/2 in b: 
            isum=isum+1
for ir in r:
    for ib in b:
        if (ir+ib)/2  in g: 
            isum=isum+1
for ig in g:
    for ib in b:
        if (ig+ib)/2  in r: 
            isum=isum+1

isum=lenr*leng*lenb-isum
                
print(isum)

### FIXED CODE ###

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

r=set()
g=set()
b=set()

for i in range(n):
    if s[i]=="R":
        r.add(i+1)
    elif s[i]=="G":
        g.add(i+1)
    else:
        b.add(i+1)

lenr=len(r)
leng=len(g)
lenb=len(b)

isum=0
for ir in r:
    for ig in g:
        if (ir+ig)/2 in b: 
            isum=isum+1
for ir in r:
    for ib in b:
        if (ir+ib)/2  in g: 
            isum=isum+1
for ig in g:
    for ib in b:
        if (ig+ib)/2  in r: 
            isum=isum+1

isum=lenr*leng*lenb-isum
                
print(isum)
### BUGGY CODE ###

from sys import stdin
from collections import deque, Counter, defaultdict
from fractions import gcd
import heapq

MOD = 10 ** 9 + 7
input = stdin.readline

n = int(input())
zero = 0
A, B = [], []
# mp = defaultdict(lambda: [0, 0])
mp = {}
for i in range(n):
    ai, bi = map(int, input().split())
    if ai == 0 and bi == 0:
        zero += 1
        continue

    gi = gcd(ai, bi)
    ai = ai // gi
    bi = bi // gi

    if bi < 0:
        ai = -ai
        bi = -bi
    if bi == 0 and ai < 0:
        ai = -ai
    if ai <= 0:
        ai, bi = bi, -ai
        if (ai, bi) in mp:
            mp[(ai, bi)][0] += 1
        else:
            mp[(ai, bi)] = [1, 0]
    else:
        if (ai, bi) in mp:
            mp[(ai, bi)][1] += 1
        else:
            mp[(ai, bi)] = [0, 1]

ans = 1
for key in mp:
    s, t = mp[key]
    ans *= pow(2, s, MOD) + pow(2, t, MOD) - 1
    ans %= MOD
print((zero - 1 + ans) % MOD)

### FIXED CODE ###

from sys import stdin
from collections import deque, Counter, defaultdict
# from fractions import gcd
from math import gcd
import heapq

MOD = 10 ** 9 + 7
input = stdin.readline

n = int(input())
zero = 0
A, B = [], []
# mp = defaultdict(lambda: [0, 0])
mp = {}
for i in range(n):
    ai, bi = map(int, input().split())
    if ai == 0 and bi == 0:
        zero += 1
        continue

    gi = gcd(ai, bi)
    ai = ai // gi
    bi = bi // gi

    if bi < 0:
        ai = -ai
        bi = -bi
    if bi == 0 and ai < 0:
        ai = -ai
    if ai <= 0:
        ai, bi = bi, -ai
        if (ai, bi) in mp:
            mp[(ai, bi)][0] += 1
        else:
            mp[(ai, bi)] = [1, 0]
    else:
        if (ai, bi) in mp:
            mp[(ai, bi)][1] += 1
        else:
            mp[(ai, bi)] = [0, 1]

ans = 1
for key in mp:
    s, t = mp[key]
    ans *= pow(2, s, MOD) + pow(2, t, MOD) - 1
    ans %= MOD
print((zero - 1 + ans) % MOD)
### BUGGY CODE ###

from collections import Counter
import itertools

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n, x, y = map(int, input().split())
d = [[float("inf")]*n for i in range(n)] 

for i in range(n-1):
    d[i][i+1] = 1
    d[i+1][i] = 1
d[x-1][y-1] = 1
d[y-1][x-1] = 1
for i in range(n):
    d[i][i] = 0
warshall_floyd(d)
D = Counter(list(itertools.chain.from_iterable(d)))
for i in range(1, n):
    print(D[i]//2)

### FIXED CODE ###

import collections
n, x, y = map(int, input().split())
d = [[0]*(i+1) for i in range(n)]
x -= 1
y -= 1
for i in range(n):
    for j in range(i+1):
        d[i][j] = min(i-j, abs(x-j)+abs(y-i)+1)
L = []
for i in range(n):
    for dd in d[i]:
        L.append(dd)
C = collections.Counter(L)
for i in range(1, n):
    print(C[i])
### BUGGY CODE ###

#!/usr/bin/env python
x, y, z, k = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
D = []
E = []
for b in B:
    for c in C:
        D.append(b+c)
D.sort(reverse=True)
n = 0
for a in A:
    for d in D[:k]:
       E.append(a+d)
E.sort(reverse=True)
for e in E[:k]:
    print(e)

### FIXED CODE ###

#!/usr/bin/env python
import numpy as np
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
D = []
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
for i in range(min(K,X)):
    for j in range(min((K//(i+1),Y))):
        for k in range(min(((K//(i+1)+1)//(j+1)),Z)):
            D.append(A[i]+B[j]+C[k])
D.sort(reverse=True)
for i in range(K):
    print(int(D[i]))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
L = LIST()

cnt = [0]*(10**3+1)
for x in L:
	cnt[x] += 1

cnt = list(accumulate(cnt))

ans = 0
for x, y in combinations(L, 2):
	ans += cnt[min(x+y-1, 1000)] - cnt[abs(x-y)] - (abs(x-y) < x < x+y) - (abs(x-y) < y < x+y)

print(ans//3)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2, log
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
from decimal import Decimal
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
from decimal import *

N = INT()
L = LIST()

cnt = [0]*(10**3+1)
for x in L:
	cnt[x] += 1

cnt = list(accumulate(cnt))

ans = 0
for x, y in combinations(L, 2):
	ans += cnt[min(x+y-1, 1000)] - cnt[abs(x-y)] - (abs(x-y) < x < x+y) - (abs(x-y) < y < x+y)

print(ans//3)
### BUGGY CODE ###

n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
mod = 10**9 + 7
dp = [[1]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j]*(s[i] != t[j])) % mod
print(dp[n][m])

### FIXED CODE ###

n,m = map(int,input().split())
s = list(map(int,input().split()))
t = list(map(int,input().split()))
mod = 10**9 + 7
dp = [[1]*(m+1) for _ in range(n+1)]
for i in range(n):
  for j in range(m):
    dp[i+1][j+1] = (dp[i][j+1] + dp[i+1][j] - dp[i][j]*(s[i] != t[j])) % mod
print(dp[n][m])
### BUGGY CODE ###

# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


import bisect
n = int(input())
a = list(map(int, input().split()))
ca = [None] * n #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s
    
def sub(l, init):
    if len(l)==0:
        return 0,0
    elif len(l)==1:
        return 0,l[0]-init
    target = (init + l[-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[-1]-l[i])
    p2 = (l[i-1]-init, l[-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca[:i], 0)
    p2 = sub(ca[i:], ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
    best = min(best, nn)
print(best)

### FIXED CODE ###

# ARC100D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


# import numpy as np
import bisect
n = int(input())
a = list(map(int, input().split()))
# a = np.array(list(map(int, input().split())))
ca = [None] * n #ca[i] = a0~aiの和
s = 0
for i,num in enumerate(a):
    s += a[i]
    ca[i] = s
# ca = a.cumsum()

def sub(l, start, end, init):
    if len(l)==0:
        return 0,0
    elif end-start==1:
        return 0,l[start]-init
    target = (init + l[end-1])/2
    i = bisect.bisect_right(l, target)
    p1 = (l[i]-init, l[end-1]-l[i])
    p2 = (l[i-1]-init, l[end-1]-l[i-1])
    if abs(p1[0] - p1[1]) < abs(p2[0] - p2[1]):
        return min(p1), max(p1)
    else:
        return min(p2), max(p2)
best = 10**15
for i in range(1,n):
    p1 = sub(ca, 0, i, 0)
    p2 = sub(ca, i, n, ca[i-1])
    nn = max(p1[1]-p2[0], p2[1]-p1[0], p1[1]-p1[0], p2[1]-p2[0])
#     print(p1,p2,nn)
    best = min(best, nn)
print(best)
### BUGGY CODE ###


from fractions import gcd

n, m = map(int, input().split())

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

ans = -1
b = [0] * n
for i in range(n):
    if a[i] % 2 != 0:
        ans = 0
        break

    else:
        b[i] = a[i] // 2


    if i == 0:
        num = format(a[i], 'b')[::-1].find('1')

    else:
        if format(a[i], 'b')[::-1].find('1') != num:

            ans = 0
            break
        else: num = format(a[i], 'b')[::-1].find('1')


if ans != 0:
    g = b[0]
    for i in range(1,n):

        g = (g*b[i]) // gcd(b[i],g)

    if g > m: ans = 0
    else:
        ans = 1
        g1 = g
        while 1:
            g += 2*g1
            if g > m: break
            else: ans += 1

print(ans)

### FIXED CODE ###

from fractions import gcd
n, m = map(int, input().split())

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

ans = -1
b = [0] * n
for i in range(n):
    if a[i] % 2 != 0:
        ans = 0
        break

    else:
        b[i] = a[i] // 2


    if i == 0:
        num = format(a[i], 'b')[::-1].find('1')

    else:
        if format(a[i], 'b')[::-1].find('1') != num:
            ans = 0
            break
        else:
            num = format(a[i], 'b')[::-1].find('1')


if ans != 0:
    g = b[0]
    for i in range(1,n):

        g = (g*b[i]) // gcd(b[i],g)

    if g > m: ans = 0
    else:
        ans = (1 + (m-g)//(2*g))

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

N = int(input())
A = list(map(int, input().split()))
A_ = [0] * (N+1)
for a in A:
    A_[a] += 1
A_ = sorted(A_)
c = 0
for i in range(N+1):
    A_[i] = c = A_[i] + c
A_.reverse()

Ans = [float("inf")] * (N+1)
for i in range(N):
    for j, a in enumerate(A_):
        d = a//(i+1)
        #print(d, end=" ")
        Ans[i+j] = min(Ans[i+j], d)
        if d==0:
            break
    #print()
print("\n".join(map(str, Ans[:-1])))


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = [0] * (N+1)
    Cnt_A = [0] * (N+1)
    for a in A:
        Cnt_A[a] += 1
        cnt = Cnt_A[a]
        C[cnt] += 1
    cum_C = []
    cu = 0
    for c in C:
        cu += c
        cum_C.append(cu)
    Ans = []
    for k in range(1, N+1):
        # K = k のとき、 n 組以上作れる <=> 使えるカードが nk 枚以上
        # n 組以上作れる <=> 同じカードは n 枚以下
        # 同じカードは n 枚以下で全体として nk 枚以上用意できるか？
        ok, ng = 0, N//k+1
        while ok + 1 < ng:
            n = ok+ng>>1
            if cum_C[n] >= n*k:
                ok = n
            else:
                ng = n
        Ans.append(ok)
    print("\n".join(map(str, Ans)))

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

    # *** 入力
    # N: 文字列の長さ
    # S: 文字列
    # *** 出力
    # sa[i]: SuffixArray
    N=int(input())
    S=input()

    import functools

    *SC, = map(ord, S+"$")

    *sa, = range(N)

    L = N + 1
    rh = [0]*(L + 1)
    md = [1]*(L + 1)
    MOD = 2147483647
    base = 37
    rev = pow(base, MOD-2, MOD)
    for i in range(1, L + 1):
        md[i] = md[i-1] * rev % MOD
    cA = ord('a')
    for i in range(L):
        rh[i+1] = (rh[i] * base + (SC[i] - cA)) % MOD

    # lcp(i, j): S[i:] と S[j:] の最長共通接頭語(LCP)の長さを求める
    def lcp(i, j):
        left = 0
        right = N+1 - max(i, j)
        v = (rh[i]-rh[j]) % MOD
        while left+1 < right:
            mid = (left + right) >> 1
            if (rh[i+mid]-rh[j+mid])*md[mid] % MOD == v:
                left = mid
            else:
                right = mid
        return left

    def cmp(a, b):
        k = lcp(a, b)
        return SC[a+k] - SC[b+k]
    sa.sort(key=functools.cmp_to_key(cmp))

    ans=0
    for i in range(N):
        for j in range(i+1,N):
            ans=max(ans,min(j-i,lcp(i,j)))

    print(ans)


resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://qiita.com/drken/items/dc53c683d6de8aeacf5a#dp-%E5%AE%9F%E8%A3%85%E3%81%AE%E9%A0%86%E5%BA%8F
    
    
    INF = 10**10  # INF+INFを計算してもオーバーフローしない範囲で大きく
    
    N = int(input())
    S=input()
    # dpテーブル dp[i][j]:= ...
    dp = [[0]*N for _ in range(N)]
    
    # 初期条件
    dp[0][0] = 0
    for i in range(N-1):
        if S[i]==S[N-1]:
            dp[N-1][i]=1


    # ループ
    for i in reversed(range(N-1)):
        for j in reversed(range(N-1)):
            if i>j:
                if S[i]!=S[j]:
                    dp[i][j]=0
                else:
                    dp[i][j]=min(i-j,dp[i+1][j+1]+1)
    
    ans=0
    for i in reversed(range(N)):
        for j in reversed(range(N)):
            if i>j:
                ans=max(ans,dp[i][j])
    print(ans)

    
    
resolve()
### BUGGY CODE ###

from itertools import combinations
N=int(input())
arr=list(map(int,input().split()))

ans=0
for i in combinations(arr,3):
    a,b,c=i[0],i[1],i[2]
    if a<b+c and c<b+a and b<a+c:
        ans+=1
        
print(ans)


### FIXED CODE ###

import bisect
N=int(input())
arr=list(map(int,input().split()))

arr.sort()

ans=0

for i in range(N-2):
    for j in range(i+1,N-1):
        k=bisect.bisect_left(arr,arr[i]+arr[j])
        if k>j:
            ans+=k-j-1
        else:
            pass
print(ans)
### BUGGY CODE ###

def gcd(a, b):
  if b > a:
    temp = b
    b = a
    a = temp
  if a % b == 0:
    return b
  else:
    return gcd(b, a % b)

def sum_of_gcd(k):
  ans = 0
  for i in range(1, k + 1):
    for j in range(1, k + 1):
      for k in range(1, k + 1):
        ans += gcd(i, gcd(j, k))
  return ans

n = int(input())
print(sum_of_gcd(n))
        

### FIXED CODE ###

def gcd(a, b):
  if b > a:
    temp = b
    b = a
    a = temp
  if a % b == 0:
    return b
  else:
    return gcd(b, a % b)
def sum_of_gcd(k):
  ans = 0
  for i in range(1, k + 1):
    for j in range(1, k + 1):
      for k in range(1, k + 1):
        if i < j and j < k:
          ans += gcd(i, gcd(j, k)) * 6
        elif i < j and j == k:
          ans += gcd(i, gcd(j, k)) * 3
        elif i == j and j < k:
          ans += gcd(i, gcd(j, k)) * 3
        elif i == j and j == k:
          ans += gcd(i, gcd(j, k))
  return ans
 
n = int(input())
print(sum_of_gcd(n))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
IJK = [0,0,0]
for i in range(N):
    IJK[a[i]-1]+=1

dp = [[[0]*(N+3) for _ in range(N+3)] for _ in range(N+3)]

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k == 0: continue
            dp[i][j][k] += N
            if i-1>=0: dp[i][j][k] += i*dp[i-1][j][k]
            if j-1>=0: dp[i][j][k] += j*dp[i+1][j-1][k]
            if k-1>=0: dp[i][j][k] += k*dp[i][j+1][k-1]
            dp[i][j][k]/=(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])




### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
IJK = [0,0,0]
for i in range(N):
    IJK[a[i]-1]+=1

dp = [[[0.0]*(N+3) for _ in range(N+3)] for _ in range(N+3)]

for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if i+j+k > N: continue
            if i+j+k == 0: continue
            tmp = 1.0*N
            if i>0: tmp += i*dp[i-1][j][k]
            if j>0: tmp += j*dp[i+1][j-1][k]
            if k>0: tmp += k*dp[i][j+1][k-1]
            dp[i][j][k] = tmp/(i+j+k)
print(dp[IJK[0]][IJK[1]][IJK[2]])
### BUGGY CODE ###

import numpy
N, M = map(int, input().split())
ship = numpy.array([list(map(int, input().split())) for _ in range(M)])

ans = 'IMPOSSIBLE'
for s1 in ship[ship.T[0] == 1]:
    for s2 in ship[ship.T[0] == s1[1]]:
        if s2[1] == N:
            ans = 'POSSIBLE'
            break

print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
ship = [list(map(int, input().split())) for _ in range(M)]

s1 = [False] * N
sN = [False] * N

for i, s in enumerate(ship):
    if s[0] == 1:
        s1[s[1] - 1] = True

    if s[1] == N:
        sN[s[0] - 1] = True

ans = 'IMPOSSIBLE'
if any([p1 * pN for p1, pN in zip(s1, sN)]):
    ans = 'POSSIBLE'

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

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力 <int> list[]
P = list(map(int, input().split()))

count = 0

for i in range(N):
    pi = P[0:i + 1]
    pi.sort()
    if pi[0] == P[i]:
        count += 1

print(count)


### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力 <int> list[]
P = list(map(int, input().split()))

count = 0
comp = 2 * (10**5)

for i in range(N):
    if comp >= P[i]:
        count += 1
        comp = P[i]

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

K,S = list(map(int,input().split(" ")))
c=0
for X in range(K+1):
    for Y in range(K+1):
        for Z in range(K+1):
            if X+Y+Z==S:
                c+=1
print(c)    

### FIXED CODE ###

K,S = list(map(int,input().split(" ")))
c=0
for X in range(K+1):
    for Y in range(K+1):
        if 0<=S-X-Y<=K:
            c+=1
print(c)
### BUGGY CODE ###

n = int(input())
l_list = list(map(int,input().split()))
count = 0
for a in range(n):
    for b in range(a+1,n):
        for c in range(b+1,n):
            if (l_list[a]<l_list[b]+l_list[c]) and (l_list[b]<l_list[c]+l_list[a]) and (l_list[c]<l_list[a]+l_list[b]):
                count += 1
print(count)


### FIXED CODE ###

from bisect import bisect_left
n = int(input())
l_list = list(map(int,input().split()))
l_list.sort()
count = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        count += bisect_left(l_list,l_list[i]+l_list[j]) - j - 1

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

import numpy as np
N,K = map(int,input().split())
res = list(map(int,input().split()))
# res = [0]*N
for k in range(K):
    delta = np.zeros((N+1), dtype=np.int32)
    for i,val in enumerate(res):
        left = max(0, i-val)
        right = min(N, i+val+1)
        delta[left] += 1
        delta[right] -= 1
    res = np.cumsum(delta, dtype=np.int32)[:N]
    # print(k)
    if delta[0] == -delta[N] == N:
        break
print(*res)



### FIXED CODE ###

N, K = map(int, input().split())
s = input()
res = list(map(int,s.split()))

for k in range(K):
    delta = [0]*(N+1)
    for i,val in enumerate(res):
        left = max(0, i-val)
        right = min(N, i+val+1)
        delta[left] += 1
        delta[right] -= 1
    res = [0]*N
    res[0] = delta[0]
    for i in range(N-1):
        res[i+1] = res[i]+delta[i+1]
    if delta[0] == -delta[N] == N:
        break

print(*res)
### BUGGY CODE ###

num ,m =map(int,input().split())
if num == 1:
    s = int(input())
    print(s//(2**m))
    
else:
    arr = sorted(list(map(int,input().split())),reverse=True)

    for i in range(m):
        for j in range(len(arr)-1):
            if arr[j]//2 >= arr[j+1]:
                arr[j] = arr[j] //2
                break
            else:
                arr[j] = arr[j] //2
                
                if arr[j] < arr[j+1]:
                    arr[j],arr[j+1] = arr[j+1],arr[j]
                    if len(arr) >= j+3:
                        if arr[j+1] < arr[j+2]:
                            arr = sorted(arr,reverse=True)
                break

    print(sum(arr))
        

### FIXED CODE ###

import heapq as hq

num ,m =map(int,input().split())

arr = [-i for i in list(map(int,input().split()))]
hq.heapify(arr)

for i in range(m):
    hq.heappush(arr, -1*(-1*hq.heappop(arr)//2))

    
print(-1*sum(arr))
### BUGGY CODE ###

N,M = map(int,input().split())
card = list(map(int,input().split()))
for i in range(M):
    card = sorted(card)
    B,C = map(int,input().split())
    for j in range(B):
        if card[j] <= C:
            card[j] = C
        else:
            pass
print(sum(card))

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
BC = [list(map(int,input().split())) for i in range(M)]
BC.sort(key = lambda x:-x[1])

index = 0
for i in range(len(BC)):
    for j in range(BC[i][0]):
        if index == len(A) or A[index] >= BC[i][1]:
            break

        else:
            A[index] = BC[i][1]
            index += 1

print(sum(A))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000000)

n,q=map(int,input().split())

tree = [[] for _ in range(n)]
ope = [0]*n
opef=[False]*n
ret=[0]*n

for i in range(n-1):
    a,b=map(int,input().split())
    tree[a-1].append(b-1)

def counter(target,num):
    global ret
    global ope
    global opef
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        tmp=0
        if opef[i]==False:
            tmp=ope[i]
            opef[i]=True
        counter(i,num+tmp)

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

counter(0,ope[0])

print(*ret)

### FIXED CODE ###

n,q = map(int,input().split())
rl = [0] * n
al = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a -1
for j in range(q):
    p,x = map(int,input().split())
    al[p-1] += x
for k in range(1,n):
    al[k] += al[rl[k]]
print(*al)
### BUGGY CODE ###

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

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

def waribiki(X,Y):
    return X//(2**Y)

while M>0:
    maxIdx = A.index(max(A))
    A[maxIdx] = waribiki(A[maxIdx],1)
    M -= 1
    

print(sum(A))


### FIXED CODE ###

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

def intm(x):
    return int(x)*-1
A = list(map(intm, input().split()))

import heapq

heapq.heapify(A)
while M>0:
    a = -heapq.heappop(A) // 2
    heapq.heappush(A,-a)
    M -= 1
   

print(-sum(A))
### BUGGY CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

from functools import lru_cache
@lru_cache(maxsize = None)
def f(s):
    # 分けない場合
    p = 0
    for i in range(N):
        for j in range(i + 1, N):
            if (s >> i) & 1 and (s >> j) & 1:
                p += a[i][j]
    t = s
    while True:
        t = (t - 1) & s
        if not t:
            break
        p_ = f(t) + f(t ^ s)
        if p < p_:
            p = p_
    return(p)

N = int(input()) # 1 <= N <= 16
a = [list(map(int, input().split())) for _ in range(N)]
print(f(2 ** (N + 1) - 1))


### FIXED CODE ###

# coding: utf-8

import sys
input = sys.stdin.readline

def f(s):
    if flag[s]:
        return(memo[s])
    # 分けない場合
    p = 0
    for i in range(N):
        for j in range(i + 1, N):
            if (s >> i) & 1 and (s >> j) & 1:
                p += a[i][j]
    t = s
    while True:
        t = (t - 1) & s
        if not t:
            break
        p_ = f(t) + f(t ^ s)
        if p < p_:
            p = p_
    flag[s] = 1
    memo[s] = p
    return(p)

N = int(input()) # 1 <= N <= 16
a = [list(map(int, input().split())) for _ in range(N)]
memo = [0] * (1 << N)
flag = [0] * (1 << N)
print(f((1 << N) - 1))