Harryxun/stf_run huggingface dataset:
# TLEするはず
def main():
    N = int(input())
    X = input()
    t = X.count("1")
    d1 = []
    d2 = []
    d11 = 1
    d22 = 1
    for i in range(1, N+1):
        d1.append(d11)
        d11 *= 2
        d11 %= t-1
        d2.append(d22)
        d22 *= 2
        d22 %= t+1
    V = int(X, 2)
    for i in range(N):
        x = 0
        cur_bits = 0
        if t != 1 and X[i] == "1":
            cur_bits = t - 1
            x = V ^ d1[N-i-1]
        elif t != 1:
            cur_bits = t + 1
            x = V ^ d2[N-i-1]
        else:
            x = 0
        ans = 0
        while x > 0:
            x = x % cur_bits
            ans += 1
            cur_bits = 0
            T = "{:0b}".format(x)
            for t in T:
                if t == "1":
                    cur_bits += 1
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# わからんわからんわからんわからんわからん
# なんで1500人も解いてんの？この界隈天才しかおらん
table = [0 for i in range(2*10**5+5)]
for i in range(2*10**5+5):
    table[i] = "{:0b}".format(i).count("1")


def main():
    N = int(input())
    X = input()
    t = X.count("1")
    x1, x2 = int(X, 2) % (t+1), int(X, 2) % (t-1) if t != 1 else 0
    for i in range(N):
        ans = 1
        x = 0
        if X[i] == "0":
            # 反転してt+1
            p = pow(2, N-i-1, t+1)
            x = x1 + p
            x %= t+1
        elif t != 1:
            p = pow(2, N-i-1, t-1)
            x = x2 - p
            x %= (t-1)
        else:
            ans = 0
        while x > 0:
            x %= table[x]
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()
n = int(input())
a = list (int(input()))

cnt = 0
for i in range (1, len(a)-1):
  if (a[i-1]<a[i]<a[i+1]) or (a[i-1]>a[i]>a[i+1]):
    cnt += 1
    
print(cnt)    


### FIXED CODE ###

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

for i in range ( 1, len(a)-1):
  if (a[i-1]<a[i]<a[i+1]) or (a[i+1]<a[i]<a[i-1]):
    cnt += 1
    
print (cnt)
s = input()
t = len(s)
print(s[0] + t + s[- 1])

### FIXED CODE ###

s = input()
t = len(s) - 2
print(s[0] + str(t) + s[- 1])
K, N = map(int, input().split())
A = list(map(int, input().split()))

for i in range(N):
    dif = A[i+1]-A[i]

dif.extend([K-A[N]])

print(K-max(dif))

### FIXED CODE ###

k,n = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
c = a[0] + (k - a[n-1])
for i in range(1,n):
  c = max(c,a[i] - a[i-1])
print(k-c)
import itertools

def sign(num):
    if num < 0:
        return -1
    elif num > 0:
        return 1
    else:
        return 0

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

signs = [-1,1]
a_sum = 0
changes_1 = 0
for i, a in enumerate(a_i):
    a_sum += a
    if sign(a_sum) != signs[i%2]:
        changes_1 += abs(a_sum) + 1
        a_sum = signs[i%2]

signs = [1,-1]
a_sum = 0
changes_2 = 0
for i, a in enumerate(a_i):
    a_sum += a
    if sign(a_sum) != signs[i%2]:
        changes_2 += abs(a_sum) + 1
        a_sum = signs[i%2]

print(min(changes_1,changes_2))

### FIXED CODE ###

S = input()
out = ""
for s in S.split():
    out += s[0].upper()
print(out)
class UnionFind():
    # 負の値は根で集合の個数
    # 正の値は次の要素を返す
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        self.table[x] = self.find(self.table[x])
        return self.table[x]
        # while self.table[x] >= 0:
        #     #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
        #     x = self.table[x]
        # return x

    # 併合
    def union(self, x, y):
        s1 = self.find(x)  # 代表のIndexを取得する
        s2 = self.find(y)
        if s1 != s2:  # 代表のIndexが違う場合
            if self.table[s1] < self.table[s2]:  # 要素数の多い方へMergeする
                self.table[s2] += self.table[s1]  # 子の和を増やす(-)
                self.table[s1] = s2  # Mergeされる側の代表をする側のインデックスに
            else:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
        return

    def size(self, x):
        # while self.table[x] >= 0:
        #     #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
        #     x = self.table[x]
        return -self.table[self.find(x)]


N, M = [int(n) for n in input().split()]
X = [0]*M
Y = [0]*M
Z = [0]*M
UF = UnionFind(N)
adj = [[0, []] for _ in range(N)]
for i in range(M):
    X[i], Y[i], Z[i] = [int(n) for n in input().split()]
    Z[i] %= 2
    X[i] -= 1
    Y[i] -= 1
    UF.union(X[i], Y[i])
s = set([UF.find(0)])
ans = 1

for i in range(1, N):
    tmp = UF.find(i)
    if not(tmp in s):
        ans += 1
        s.add(tmp)
print(ans)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)


N, M = [int(n) for n in input().split()]
X = [0]*M
Y = [0]*M
Z = [0]*M
UF = UnionFind(N)
adj = [[0, []] for _ in range(N)]
for i in range(M):
    X[i], Y[i], Z[i] = [int(n) for n in input().split()]
    Z[i] %= 2
    X[i] -= 1
    Y[i] -= 1
    UF.union(X[i], Y[i])
s = set([UF.find(0)])
ans = 1

for i in range(1, N):
    tmp = UF.find(i)
    if not(tmp in s):
        ans += 1
        s.add(tmp)
print(ans)
s=input()
print(s.count("1")

### FIXED CODE ###

s=input()
print(s.count("1"))
import sys
n, m = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

pars = [-1]*n

def get_root(x):
    if pars[x] < 0:
        return x
    else:
        pars[x] = get_root(pars[x])
        return pars[x]

def combine(x, y):
    if x == y:
        return
    r_x = get_root(x)
    r_y = get_root(y)
    if r_x > r_y:
        r_x, r_y = r_y, r_x
    if r_x != r_y:
        pars[r_x] += pars[r_y] # 足して経路長を求めるのに使う
        pars[r_y] = r_x

def size(x):
    return -pars[get_root(x)]

for x, y in info:
    combine(x, y)

print(-min(pars))


### FIXED CODE ###

import sys


class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x


N, M = map(int, input().split())
info = [tuple(map(int, s.split())) for s in sys.stdin.readlines()]

uf = UnionFind(N)
for a, b in info:
    a -= 1; b -= 1
    uf.union(a, b)

ans = min(uf.parents)

print(-ans)
from sys import stdin

K = int(stdin.readline().rstrip())
if K % 2 = 0:
  print(-1)
a_n = 7
i = 1
while True:
  if a_n < K:
    print(-1)
    break
  if a_n % K == 0:
    print(i)
    break
  else:
    i += 1
    a_n = a_n * 10 + 7
    



### FIXED CODE ###

from sys import stdin
K = int(stdin.readline().rstrip())
def main(K):
  a=0
  for i in range(1,K+1):
    a = ((10%K) * a + 7)%K
    if a == 0:
      return i
  return -1
print(main(K))
A = list(map(int, input().split()))

cnt = 0
for i in A:
  if i != 7 or i !=5:
  	print('NO')
  else i == 7:
    cnt += 1

if cnt == 1:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

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

cnt = 0
for i in A:
  if i != 7 and i !=5:
  	cnt = 5
  elif i == 7:
    cnt += 1

if cnt == 1:
  print('YES')
else:
  print('NO')
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    ans = []
    AB = [[] for _ in range(N+1)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        AB[a].append(b)
        AB[b].append(a)
    
    M = max([len(i) for i in AB])
    _c = set(range(1, M+1))
    C = [_c for _ in range(N+1)]

    root = 1
    checked = set()
    q = [root]

    while q:
        i = q.pop(0)
        if i in checked:
            continue
        checked.add(i)
        for j in AB[i]:
            if j in checked:
                continue
            k = C[i].pop()
            ans.append(k)
            C[j] = C[j] - set([k])
            q.append(j)

    print(M)   
    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


N = int(readline())
graph = [[] for _ in range(N+1)]
AB = []

for _ in range(N-1):
    a, b = map(int, readline().split())
    AB.append((a, b))
    graph[a].append(b)
    graph[b].append(a)

parent = [0] * (N+1)
root = 1
stack = [root]
color = [0] * (N+1)
while stack:
    x = stack.pop()
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        parent[y] = x
        color[y] = c
        c += 1
        stack.append(y)

print(max(color))

for a, b in AB:
    if parent[a] == b:
        print(color[a])
    else:
        print(color[b])
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


s = [ord(n) for n in S()]
t = [ord(n) for n in S()]

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i][j + 1])
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

# 最長共通部分列の長さ
# print(dp[-1][-1])

ans = ''
i = len(s)
for j in range(len(t) + 1)[::-1]:
    if dp[i][j] != dp[i][j - 1]:
        while dp[i][j] == dp[i - 1][j]:
            i -= 1
        ans += chr(t[j - 1])
        i -= 1

print(ans[::-1])


### FIXED CODE ###

# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()


s = [ord(n) for n in S()]
t = [ord(n) for n in S()]

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = max(dp[i][j] + 1, dp[i][j + 1])
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

# 最長共通部分列の長さ
# print(dp[-1][-1])

ans = ''
i = len(s)
for j in range(len(t) + 1)[::-1]:
    if dp[i][j] != dp[i][j - 1]:
        if i == 0 or j == 0: break
        while dp[i][j] == dp[i - 1][j]:
            i -= 1
        ans += chr(t[j - 1])
        i -= 1

print(ans[::-1])
A, B = int(input().split())

max = -1000
if A + B > max:
    max = A + B
if A - B > max:
    max = A - B
if A * B > max:
    max = A * B
print(max)

### FIXED CODE ###

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

max = -1000
if A + B > max:
    max = A + B
if A - B > max:
    max = A - B
if A * B > max:
    max = A * B
print(max)
A = [int(i) for i in raw_input().split()]
N = len(A)
A0 = [A[i] for i in xrange(0, N, 2)]
A1 = [A[i] for i in xrange(1, N, 2)]

Count = 0
S0 = set(A0)
S1 = set(A1)
N0 = []
N1 = []

for s in S0:
    N0.append((s, sum(map(lambda x: x==s, A0))))

for s in S1:
    N1.append((s, sum(map(lambda x: x==s, A1))))

N0.sort(key=lambda x: x[1], reverse=True)
N1.sort(key=lambda x: x[1], reverse=True)

if N0[0][0] == N1[0][0]:
    if N0[0][0] < N1[0][0]:
        if len(N0) == 1:
            print N - N1[0][1]
        else:
            print N - N0[1][1] - N1[0][1]
    else:
        if len(N1) == 1:
            print N - N0[0][1]
        else:
            print N - N0[0][1] - N1[1][1]
else:
    print N - N0[0][1] - N1[0][1]


### FIXED CODE ###


from collections import Counter

n    = int(raw_input())
nums = list(map(int, raw_input().split()))

nums_odd  =   nums[0:n:2]
nums_even =   nums[1:n:2]

N_odd     =   sorted(Counter(nums_odd ).items(), key=lambda x: x[1], reverse=True) + [(-1,0)]
N_even    =   sorted(Counter(nums_even).items(), key=lambda x: x[1], reverse=True) + [(-1,0)]

if N_odd[0][0] == N_even[0][0]:
    if N_odd[0][1] + N_even[1][1] > N_odd[1][1] + N_even[0][1]:
        print n - N_odd[0][1] - N_even[1][1]
    else:
        print n - N_odd[1][1] - N_even[0][1]
else:
    print n - N_odd[0][1] - N_even[0][1]
# -*- coding: utf-8 -*-
from collections import deque
from heapq import heappush, heappop, heapify, merge
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]

def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)

D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])

H = []
S = deque([]) # single
for k, v in D.items():
    if len(v) == 1:
        S.append(v)
    else:
        H.append(sorted(v))

heapify(H)

res = 0 
while True:
    if (len(H) == 0) or (len(S) + len(H) <= 1):
        break
    
    if len(S) > 1:
        A = S.popleft()
    else:
        if len(H) <= 1:
            break
        A = heappop(H)

    B = heappop(H)

    res += A[0] + B[0]
    C = list(merge(A[1:], B[1:]))

    if len(C) == 1:
        S.append(C)
    elif len(C) == 0: # ありえないはず
        pass
    else:
        heappush(H, C)

ok = True
if len(S) > 2:
    print("Impossible")
    ok = False
elif len(S) == 2:
    res += S[0]+S[1]
elif len(S) == 1:
    A = S[0]
    if len(H) == 1:
        B = heappop(H)
        res += A[0] + B[0]
else:
    pass
if ok:
    print(res)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)
def inpl(): return tuple(map(int, input().split()))
 
N, M = inpl()
A = inpl()
tree = [[-1, 1]  for _ in range(N)] # [next, rank]
 
def find(i):
    if tree[i][0] == -1:
        group = i
    else:
        group = find(tree[i][0]) 
        tree[i][0] = group
    return group
  
def unite(x, y):
    px = find(x)
    py = find(y)
      
    if tree[px][1] == tree[py][1]: # rank is same
        tree[py][0] = px
        tree[px][1] += 1
    else:
        if tree[px][1] < tree[py][1]:
            px, py = py, px
        tree[py][0] = px
  
for _ in range(M):
    x, y = tuple(map(int, input().split()))
    if not int(find(x) == find(y)):
        unite(x, y)
 
D = defaultdict(list)
for n in range(N):
    D[find(n)].append(A[n])
 
H = []
res = 0 

for k, v in D.items():
    v = sorted(v)
    res += v[0]
    H.extend(v[1:])
 
if N < 2*(N-M-1):
    print("Impossible")
elif M == N-1:
    print(0)
else:
    res += sum(sorted(H)[:2*(N-M-1) - len(D.keys())])
    print(res)
def actual(r):
    return 2 * r * math.pi

r = int(input())
print(actual(r))

### FIXED CODE ###

import math


def actual(r):
    return 2 * r * math.pi

r = int(input())
print(actual(r))
# -*- coding: utf-8 -*-
"""
Created on Wed Mar  6 16:29:39 2019

@author: Yamazaki Kenichi
"""

H,W = map(int,input().split())
A = [input() for i in range(H)]
T = [[-1,0,0] for j in range(H*W)] 

def g(x,i,j):
    if x == '.':
        return 1 if (i+j)%2 == 0 else 2
    else:
        return 4 if (i+j)%2 == 0 else 3
def p(u):
    return T[u][0]
def findset(u):
    if p(u) == -1:
        return u
    else:
        T[u][0] = findset(p(u))
        return T[u][0]

def unite(u,v):
    if findset(u) == findset(v):
        return
#    if T[findset(u)[0]][findset(u)[1]][1]+T[findset(u)[0]][findset(u)[1]][0
#         ] >= T[findset(v)[0]][findset(v)[1]][0]+T[findset(v)[0]][findset(v)[1]][1]:
    T[findset(u)][1] += T[findset(v)][1]
    T[findset(u)][2] += T[findset(v)][2]
    T[findset(v)][0] = findset(u)
def unite_check(i1,j1,i2,j2):
    if g(A[i1][j1],i1,j1)%2 == 0 and g(A[i2][j2],i2,j2)%2 == 0:
        unite(i1 * H + j1, i2 * H + j2)
    elif g(A[i1][j1],i1,j1)%2 == 1 and g(A[i2][j2],i2,j2)%2 == 1:
        unite(i1 * H + j1, i2 * H + j2)

for i in range(H):
    for j in range(W):
        if g(A[i][j],i,j) <= 2:
            T[i * H + j][1] += 1
        else:
            T[i * H + j][2] += 1
        if i !=0:
            unite_check(i,j,i-1,j)
        if j !=0:
            unite_check(i,j,i,j-1)
ans = 0
for i in range(H):
    for j in range(W):
        if T[i * H + j][0] == -1:
            ans += T[i * H + j][1] * T[i * H + j][2]
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Mar  6 16:29:39 2019

@author: Yamazaki Kenichi
"""

H,W = map(int,input().split())
A = [input() for i in range(H)]
T = [[-1,0,0] for j in range(H*W)] 

def g(x,i,j):
    if x == '.':
        return 1 if (i+j)%2 == 0 else 2
    else:
        return 4 if (i+j)%2 == 0 else 3
def p(u):
    return T[u][0]
def findset(u):
    if p(u) == -1:
        return u
    else:
        T[u][0] = findset(p(u))
        return T[u][0]

def unite(u,v):
    if findset(u) == findset(v):
        return
#    if T[findset(u)[0]][findset(u)[1]][1]+T[findset(u)[0]][findset(u)[1]][0
#         ] >= T[findset(v)[0]][findset(v)[1]][0]+T[findset(v)[0]][findset(v)[1]][1]:
    T[findset(u)][1] += T[findset(v)][1]
    T[findset(u)][2] += T[findset(v)][2]
    T[findset(v)][0] = findset(u)
def unite_check(i1,j1,i2,j2):
    if g(A[i1][j1],i1,j1)%2 == 0 and g(A[i2][j2],i2,j2)%2 == 0:
        unite(i1 * W + j1, i2 * W + j2)
    elif g(A[i1][j1],i1,j1)%2 == 1 and g(A[i2][j2],i2,j2)%2 == 1:
        unite(i1 * W + j1, i2 * W + j2)

for i in range(H):
    for j in range(W):
        if g(A[i][j],i,j) <= 2:
            T[i * W + j][1] += 1
        else:
            T[i * W + j][2] += 1
        if i !=0:
            unite_check(i,j,i-1,j)
        if j !=0:
            unite_check(i,j,i,j-1)
ans = 0
for i in range(H):
    for j in range(W):
        if T[i * W + j][0] == -1:
            ans += T[i * W + j][1] * T[i * W + j][2]
print(ans)
s=input()
s=list(s)
if len(s)%2==0:
    s.pop(len(s)-1)
    s.pop(len(s)-1)
else:
    s.pop(len(s)-1)

while len(s)>0:
    if s[:int(len(s)/2)]==s[int(len(s)/2):]:
        print(len(s))
        sys.exit()
    s.pop(len(s)-1)
    s.pop(len(s)-1)

### FIXED CODE ###

import sys
s=input()
s=list(s)
if len(s)%2==0:
    s.pop(len(s)-1)
    s.pop(len(s)-1)
else:
    s.pop(len(s)-1)

while len(s)>0:
    if s[:int(len(s)/2)]==s[int(len(s)/2):]:
        print(len(s))
        sys.exit()
    s.pop(len(s)-1)
    s.pop(len(s)-1)
a,b,c=list(input().split())
AB=int(a)
BC=int(b)
ptint(int(AB*BC/2))

### FIXED CODE ###

a=list(input().split())
b=int(a[0])
c=int(a[1])
d=int(c*b/2)
print(d)
T=int(input())
si=[]
sum=0
for i in range(T):
  si.append(int(input()))
  sum=sum+int(input())
sorted(si)
for j in range(T):
  if si[j]%10!=0:
    sum=sum-si[j]
    break
  else:
    sum=sum-si[j]
print(sum)
  

### FIXED CODE ###

T=int(input())
si=[]
sum=0
for i in range(T):
  si.append(int(input()))
si.sort()
for k in range(T):
    sum=sum+si[k]
if sum%10!=0:
    print(sum)
else:
    for j in range(T):
        if si[j]%10!=0:
            sum=sum-si[j]
            break
        else:
            pass
    if sum%10==0:
        sum=0
    else:
        pass
    print(sum)
# 初期入力
import numpy as np
import sys
input = sys.stdin.readline
N,M = (int(i) for i in input().split())
A = list(map(int, input().split()))
A =np.array(A,dtype=int)
take =[[-1] for i in range(M)]
#num =[-1]*M
for x in range(M):
    B,C = (int(i) for i in input().split())
    take[x] =B,C
    #num[i] =C

#
A.sort()
#take =[0] +take
#num =[0] +num
take.sort(key=lambda x: x[1], reverse=True)
take =[(0,0)] +take
for i in range(1,M): #初項に「０」足したから「M]まで
    st =take[i-1][0]
    fi =take[i-1][0] +take[i][0]
    if A[st] >take[i][1]:
        break
    A[st:fi] =np.where(A[st :fi] < take[i][1] ,take[i][1],A[st:fi])
print(sum(A))

### FIXED CODE ###

# 初期入力
#import numpy as np
import sys
input = sys.stdin.readline
N,M = (int(i) for i in input().split())
A = list(map(int, input().split()))
take =[[-1] for i in range(M)]
for x in range(M):
    B,C = (int(i) for i in input().split())
    take[x] =B,C

#
A.sort()
take.sort(key=lambda x: x[1], reverse=True)
take =[(0,0)] +take
ind =[0]*(M+1)
for i in range(1,M+1): #初項に「０」足したから「M]まで
    ind[i] =ind[i-1] +take[i][0]
    if ind[i-1] >=N:
        break
    elif A[ind[i-1]] >=take[i][1]:
        break
    elif ind[i] <N and A[ind[i]] <take[i][1]: #全て一括で置き換える
        A[ind[i-1] :ind[i]] =[take[i][1] ] *(take[i][0]) 
    else:
        for j in range(ind[i-1],ind[i]): #最後は1つずつ確認しながら置き換える
            if N <= j:
                break
            if A[j] <take[i][1]:
                A[j] =take[i][1]
            else:
                break
print(sum(A))
import bisect
import math

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

ans = 0
used = [0] * N
for i in range(N-1, -1, -1):
    if used[i] == 0:
        A_i = A[i]
        comp = 2 ** math.ceil(math.log2(A_i+1)) - A_i
        j = bisect.bisect_left(A, comp, 0, i-1)
        if A[j] == comp and used[j] == 0:
            ans += 1
            used[j] = 1

print(ans)


### FIXED CODE ###

import bisect
import math
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int, input().split()))
A.sort()
A_set = []
num = []
a_cur = float('inf')
for a in A:
    if a != a_cur:
        A_set.append(a)
        num.append(1)
        a_cur = a
    else:
        num[-1] += 1

ans = 0
for i in range(len(A_set) - 1, -1, -1):
    if num[i] > 0:
        A_i = A_set[i]
        comp = 2 ** math.ceil(math.log(A_i + 1, 2)) - A_i
        j = bisect.bisect_left(A_set, comp, 0, i)
        while True:
            if A_set[j] == comp:
                if num[j] > 0:
                    if i != j:
                        ans += min(num[j], num[i])
                        num[j] = max(num[j] - num[i], 0)
                        break
                    elif num[j] >= 2:
                        add = num[j] // 2
                        ans += add
                        num[j] = num[j] % 2
                        break
                    else:
                        break
                else:
                    break
            else:
                break

print(ans)
a, b = map(int, raw_input().split())
print a*b 2*a+2*b

### FIXED CODE ###

a, b = map(int, raw_input().split())
print a*b,
print 2*a + 2*b
N = int(input())
A = list(map(int, input().split()))
Adict = []
for i in A:
    if i in Adict:
        Adict[i]=Adict[i]+1
    else:
        Adict.update({i:1})
B = [0, 0]
for i in Adict.keys():
    if Adict[i] >= 2:
        B.append(i)
    if Adict[i] >= 4:
        B.append(i)
B.sort()
print(B[-1]*B[-2])


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Adict = {}
for i in A:
    if i in Adict:
        Adict[i]=Adict[i]+1
    else:
        Adict.update({i:1})
B = [0, 0]
for i in Adict.keys():
    if Adict[i] >= 2:
        B.append(i)
    if Adict[i] >= 4:
        B.append(i)
B.sort()
print(B[-1]*B[-2])