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

import numpy as np

def split(ar, k, w):
    a = 0
    if np.sum(ar>k) > 0:
        return -1
    tm = ar[0]
    for i in range(1, w):
        tm += ar[i]
        if np.sum(tm > k) > 0:
            a += 1
            tm = ar[i]
    return a
            

h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for j in range(h)]
s = np.array(s)
ans = h*w

for i in range(2**(h-1)):
    data = []
    temp = s[0].copy()
    sp = bin(i+2**h)[4:]
    for j in range(1, h):
        if sp[j-1] == "0":
            temp += s[j]
        else:
            data.append(temp)
            temp = s[j].copy()
    data.append(temp)
    ans_ = split(np.array(data).T, k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)


### FIXED CODE ###

def add(in1, in2):
    return [a + b for a, b in zip(in1, in2)]

def check_overk(in1, k):
    return len([i for i in in1 if i>k]) > 0

def split(ar, k, w):
    a = 0
    for i in ar:
        if check_overk(i, k):
            return -1
    tm = ar[0]
    for i in range(1, w):
        tm = add(tm, ar[i])
        if check_overk(tm, k):
            a += 1
            tm = ar[i]
    return a
            

h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for j in range(h)]
ans = h*w

for i in range(2**(h-1)):
    data = []
    temp = s[0]
    sp = bin(i+2**h)[4:]
    if ans < sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp = add(temp, s[j])
        else:
            data.append(temp)
            temp = s[j]
    data.append(temp)
    ans_ = split([list(x) for x in zip(*data)], k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)
### BUGGY CODE ###

from collections import deque
s = deque(input())
q = int(input())
for i in range(q):
    x = list(input().split())
    if x [0] == '1':
        s.reverse()
    else:
        if x[1] == '1':
            s.appendleft(x[2])
        else:
            s.append(x[2])
print("".join(s))

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
rev= 0
for i in range(q):
    x = list(input().split())
    if x [0] == '1':
        rev += 1
    else:
        if x[1] == '1':
            if rev % 2 == 0:
                s.appendleft(x[2])
            else:
                s.append(x[2])
        else:
            if rev % 2 == 0:
                s.append(x[2])
            else:
                s.appendleft(x[2])
if rev % 2 == 1:
    s.reverse()
print("".join(s))
### BUGGY CODE ###

n = int(input())
s_list = [''.join(sorted(input())) for _ in range(n)]
s_set = set(s_list)
cnt = 0
for s in s_set:
    cnt += sum(range(s_list.count(s)))
print(cnt)

### FIXED CODE ###

n = int(input())
cnt = 0
s_dic = {}
for _ in range(n):
    s = ''.join(sorted(input()))
    if s in s_dic.keys():
        s_dic[s] += 1
        cnt += s_dic[s]
    else:
        s_dic[s] = 0

print(cnt)
### BUGGY CODE ###

#-*-coding:utf-8-*-

def main():
    k, s = map(int, input().split())

    ans = 0
    for i in range(k+1):
        for j in range(k+1):
            for k in range(k+1):
                if i + j + k == s:
                    ans += 1
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

def main():
    k, s = map(int, input().split())

    ans = 0
    for i in range(k+1):
        for j in range(k+1):
            if 0 <= s - (i + j) <= k:
                ans += 1
    print(ans)

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

import sys
input = sys.stdin.readline

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

from fractions import Fraction

ABS=[abs(a) for a in A]
OK=-max(ABS)**2-1
NG=max(ABS)**2+1

import bisect

while NG-OK>1:
    mid=(OK+NG)//2
    SC=0
    for i in range(N):
        if A[i]>0:
            x=bisect.bisect_left(A,Fraction(mid,A[i]))
            SC+=max(0,x-i-1)

        elif A[i]<0:
            x=bisect.bisect_right(A,Fraction(mid,A[i]))
            SC+=min(N-i-1,N-x)
        else:
            if mid>0:
                SC+=N-i-1
            else:
                SC+=0

    #print(OK,NG,mid,SC)

    if SC<=K-1:
        OK=mid
    else:
        NG=mid
        
print(OK)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

M=[]
Z=[]
P=[]

for a in A:
    if a<0:
        M.append(-a)
    elif a==0:
        Z.append(a)
    else:
        P.append(a)

M.reverse()

MINUS=len(M)*len(P)
PLUS=len(P)*(len(P)-1)//2+len(M)*(len(M)-1)//2
ZERO=N*(N-1)//2-PLUS-MINUS

if MINUS<K and K<=MINUS+ZERO:
    print(0)
    sys.exit()

if K<=MINUS:
    OK=10**18
    NG=0

    while OK-NG>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(M)):
            while NOW>=0 and mid<M[i]*P[NOW]:
                NOW-=1
            ANS+=len(P)-NOW-1

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(-OK)

else:
    OK=0
    NG=10**18
    K-=MINUS+ZERO

    while NG-OK>1:
        mid=(OK+NG)//2

        ANS=0
        NOW=len(P)-1

        for i in range(len(P)):
            while NOW>0 and mid<=P[i]*P[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        NOW=len(M)-1

        for i in range(len(M)):
            while NOW>0 and mid<=M[i]*M[NOW]:
                NOW-=1
            ANS+=max(0,NOW-i)

        if ANS>=K:
            NG=mid

        else:
            OK=mid

    print(OK)
### BUGGY CODE ###

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

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N-1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

sub_size = [[] for _ in range(N)]

def dfs(cur=0, pre=-1) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  if s != N - 1 :
    sub_size[cur].append(N - 1 - s)

  return s + 1

dfs()

power = [1]
for _ in range(N) :
  power.append(power[-1]*2%mod)

ret = 0
for i in range(N) :
  tmp = power[N-1]-1
  for ss in sub_size[i] :
    tmp -= power[ss]-1
  ret += tmp

ret = ret*pow(power[N], mod - 2, mod)% mod

print(ret)

### FIXED CODE ###

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

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

own_size = [0] * N
sub_size = [[] for _ in range(N)]

# pythonのdfs重すぎて自分でstack書かないと通らない。
# く〜〜つらいとこね、これ！！！！
stack = [(0, -1)]
for i in range(N) :
  cur, pre = stack[i]
  for nex in vec[cur] :
    if nex != pre :
      stack.append((nex, cur))

while stack :
  cur, pre = stack.pop()
  if pre != -1 :
    sub_size[pre].append(own_size[cur] + 1)
    own_size[pre] += own_size[cur] + 1
  if own_size[cur] != N - 1 :
    sub_size[cur].append(N - 1 - own_size[cur])

fac = [1]
inv = [1]
div = pow(2, mod - 2, mod)
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(inv[-1] * div % mod)

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * div % mod

print(ret)
### BUGGY CODE ###

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

for i in range(n):
    t = list(map(str,input().split()))
    if t[0] == '1':
        s = s[::-1]
    else:
        if t[1] == '1':
            s = s[::-1] + t[2]
            s = s[::-1]
        else:
            s = s + t[2]
            
print(s)

### FIXED CODE ###

s = input()
T = ""
n = int(input())
for i in range(n):
    # print(s,T)
    t = list(map(str,input().split()))
    if t[0] == "1":
        s,T = T,s
    else:
        if t[1] == "1":
            T += t[2]
        else:
            s += t[2]

print(T[::-1]+s)
### BUGGY CODE ###


def main():
    pass
    N = int(input())
    A = list(map(int, input().split()))

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

if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    pass
    N = int(input())
    A = list(map(int, input().split()))

    H = [0]*N
    for i in range(0,N):
        if i >= A[i]:
            H[i-A[i]] += 1

    ans = 0
    for k in range(0,N):
        Bk = k+A[k]
        if Bk < N:
            ans += H[Bk]

    print(ans)

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

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
bw = {1:0}

def dfs(frm, is_b):
	tmp = []
	for e in edges[:]:
		if e[0] == frm:
			tmp.append(e)
			edges.remove(e)
		elif e[1] == frm:
			tmp.append([e[1], e[0], e[2]])
			edges.remove(e)

	for t in tmp:
		if t[2] % 2 == 0:
			bw[t[1]] = is_b
		else:
			bw[t[1]] = abs(is_b - 1)
		dfs(t[1], bw[t[1]])

dfs(1, 0)

for i in range(1, n + 1):
	print(bw[i])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
edges = [list(map(int, input().split())) for _ in range(n - 1)]
bw = [-1 for i in range(n + 1)]
bw[1] = 0

new_edges = [[] for _ in range(n + 1)]

for e in edges:
	new_edges[e[0]].append([e[1], e[2]]) 
	new_edges[e[1]].append([e[0], e[2]]) 

def dfs(frm, now):
	for ne in new_edges[now]:
		if ne[0] == frm:
			continue
		else:
			if ne[1] % 2 == 0:
				bw[ne[0]] = bw[now]
			else:
				bw[ne[0]] = abs(1 - bw[now])
			dfs(now, ne[0])

dfs(0, 1)

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

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

sum = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        sum += int(a[i] ^ a[j]) % (10 ** 9 + 7)

print(sum % (10 ** 9 + 7))


### FIXED CODE ###

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

mod = 10 ** 9 + 7

j_max = 0
cnt = [0] * 60
for i in range(n):
    for j in range(60):
        cnt[j] += a[i] % 2
        a[i] = a[i] // 2
        if a[i] == 0:
            j_max = max(j_max, j)
            break

ans = 0
for i in range(j_max + 1):
    ans = (ans + (2 ** i) * cnt[i] * (n - cnt[i])) % mod

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

s = input()
x, y = map(int, input().split())

x_list = []
y_list = []

st = s.split("T")
x -= len(st[0])

for i, ls in enumerate(st[1:]):
    if i % 2:
        x_list.append(len(ls))
    else:
        y_list.append(len(ls))

dpx = [[0 for i in range(16001)] for j in range(len(x_list)+1)]
dpy = [[0 for i in range(16001)] for j in range(len(y_list)+1)]

dpx[0][8000] = 1
dpy[0][8000] = 1

for i in range(len(x_list)):
    for num in range(16001):
        if num + x_list[i] <= 16000 and dpx[i][num] == 1:
            dpx[i+1][num+x_list[i]] = 1
        if num - x_list[i] >= 0 and dpx[i][num] == 1:
            dpx[i+1][num-x_list[i]] = 1

for i in range(len(y_list)):
    for num in range(16001):
        if num + y_list[i] <= 16000 and dpy[i][num] == 1:
            dpy[i+1][num+y_list[i]] = 1
        if num - y_list[i] >= 0 and dpy[i][num] == 1:
            dpy[i+1][num-y_list[i]] = 1

if dpx[len(x_list)][x+8000] == 1 and dpy[len(y_list)][y+8000] == 1:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
x, y = map(int, input().split())

x_list = []
y_list = []

st = s.split("T")
x -= len(st[0])

for i, ls in enumerate(st[1:]):
    if i % 2:
        x_list.append(len(ls))
    else:
        y_list.append(len(ls))

def judge(xy, ls):
    dp = set([0])
    for l in ls:
        tmp = []
        for v in dp:
            tmp.append(v+l)
            tmp.append(v-l)
        dp = set(tmp)
    return xy in dp

print("Yes" if judge(x, x_list) and judge(y, y_list) else "No")
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
count = 0
for i in range(max(A)):
    if A.count(i+1) > 0:
        count += A.count(i+1) -1
N = N - 2*(count // 2 + count % 2)
print(N)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
count = [0]*max(A)
for i in A:
    count[i-1] += 1
count = [i for i in count if i != 0]
count = sum(count) - len(count)
N = N - 2*(count // 2 + count % 2)
print(N)
### BUGGY CODE ###

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)

n = k = ar = dp = 0
 
def solve(x):
	global n,k,ar,dp
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	m = 1e9
	for i in range(x+1,mn(n,x+k+1)):
		t = ab(ar[x]-ar[i])+solve(i)
		m = t if t<m else m
	dp[x] = m
	return dp[x]
 
def main():
	global n,ar,k,dp
	(n,k), ar = [[*map(int,s.split())] for s in [*open(0)]]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(0))
 
main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

n = int(input())

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


for i in range(len(argList)):
    argList2 = argList.copy()
    argList2.pop(i)
    argList2.sort()
    print(argList2[int(len(argList2)/2)])


### FIXED CODE ###

n = int(input())

argList = list(map(int, input().split()))
argList2 = argList.copy()
argList2.sort()

med_before = argList2[int(len(argList2)/2)-2]
med = argList2[int(len(argList2)/2)-1]
med_after = argList2[int(len(argList2)/2)]

for a in argList:
    if( a <= med):
        print(med_after)
    else:
        print(med)
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
ans = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            triangle = [l[i],l[j],l[k]]
            triangle.sort()
            if triangle[0]+triangle[1] > triangle[2]:
                ans += 1

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
ans = 0
l.sort()

for i in range(n-2):
    for j in range(i+1, n-1):
        c_i = bisect.bisect_left(l, l[i]+l[j])
        if c_i > j:
            ans += c_i - j - 1
        else:
            continue
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7

dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0

for i in range(2, N+1):
    if i in a:
        continue
    dp[i] += (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)

### FIXED CODE ###

N, M = map(int, input().split())
a = [int(input()) for _ in range(M)]
MOD = 10**9 + 7
 
dp = [0] * (N+1)
dp[0] = 1
dp[1] = 1 if 1 not in a else 0
 
a = set(list(range(2,N+1))) - set(a)
for i in a:
    dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[N] % MOD)
### BUGGY CODE ###

n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  #print(max_point)
  for i in range(1, n + 1):
    s = []
    f_pos = positions[i]
    score = scores[f_pos]
    s.append(score)
    while f_pos != i:
      f_pos = positions[f_pos]
      score += scores[f_pos]
      s.append(score)
    loop = len(s)
    if loop >= k:
      point = max(s[:k])
    elif s[-1] <= 0:
      point = max(s)
    else:
      loop_c = k // loop
      r = k % loop
      point1 = s[-1] * loop_c
      if r != 0:
        point1 += max(s[:r])
      point2 = s[-1] * (loop_c - 1)
      point2 += max(0, max(s))
      point = max(point1, point2)
    max_point = max(max_point, point)
  print(max_point)


### FIXED CODE ###

n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  #print(max_point)
  for i in range(1, n + 1):
    s = []
    f_pos = positions[i]
    score = scores[f_pos]
    s.append(score)
    while f_pos != i:
      f_pos = positions[f_pos]
      score += scores[f_pos]
      s.append(score)
    loop = len(s)
    if loop >= k:
      point = max(s[:k])
    elif s[-1] <= 0:
      point = max(s)
    else:
      loop_c = k // loop
      r = k % loop
      point1 = s[-1] * loop_c
      if r != 0:
        point1 += max(s[:r])
      point2 = s[-1] * (loop_c - 1)
      point2 += max(0, max(s))
      point = max(point1, point2)
    max_point = max(max_point, point)
  print(max_point)
### BUGGY CODE ###

from collections import deque

s = input()
d = deque()
num = 0
for i in s:
    d.append(i)
q = int(input())
for i in range(q):
        data = input().split()
        if len(data) == 1 :
            num += 1
        else:
            if num % 2 == 1:
                d.reverse()
            num = 0
            f = int(data[1])
            c = data[2]
            if f == 1:
                d.appendleft(c)
            else:
                d.append(c)
                
if num% 2 ==1:
    d.reverse()


s = list(d)
s = "".join(s)



print(s)

### FIXED CODE ###

from collections import deque

s = input()
d = deque()
header = 1
for i in s:
    d.append(i)
q = int(input())
for i in range(q):
        data = input().split()
        if len(data) == 1 :
            header *= -1
        else:
            f = int(data[1])
            c = data[2]
            if header == 1:
                if f == 1:
                    d.appendleft(c)
                else:
                    d.append(c)
            else:
                if f == 1:
                    d.append(c)
                else:
                    d.appendleft(c)
                
if header == -1:
    d.reverse()

s = list(d)
s = "".join(s)



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

# D - RGB Triplets
import heapq

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

R = [i for i, x in enumerate(s) if x=='R']
G = [i for i, x in enumerate(s) if x=='G']
B = [i for i, x in enumerate(s) if x=='B']

ans = 0

for r in R:
    for g in G:
        for b in B:
            mi = min(r, g, b)
            ma = max(r, g, b)
            if (r+g+b)==mi+ma+(mi+ma)/2:
                continue
            else:
                ans += 1

print(ans)

### FIXED CODE ###

# D - RGB Triplets

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

r = len([i for i, x in enumerate(s) if x=='R'])
g = len([i for i, x in enumerate(s) if x=='G'])
b = len([i for i, x in enumerate(s) if x=='B'])

ans = r * g * b

for i in range(n):
    for j in range(i+1, n):
        k = j+j-i
        if k >= n:
            break
        if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
            ans -= 1

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

N=int(input())
MOD=10**9+7
L=60
ls=[int(s) for s in input().split()]
bils=[]
for i in range(N):
  val_ls=[0 for j in range(L)]
  for j in range(L):
    if (2**j)&ls[i]>0:
      val_ls[j]=1
  bils.append(val_ls)
bisumls=[[0 for _ in range(L)] for _ in range(N)]
bisumls[N-1]=bils[N-1]
for i in range(2,N):
  for j in range(L):
    bisumls[-i][j]=bisumls[-i+1][j]+bils[-i][j]
#[[0, 0, 0], [3, 0, 2], [2, 0, 2], [2, 0, 1], [1, 0, 1]]
ans=0
for i in range(N-1):
  base=1
  #print(bils[i],bisumls[i+1])
  for k in range(L):
    if bils[i][k]==1:
      a=N-i-1-bisumls[i+1][k]
    else:
      a=bisumls[i+1][k]
   #   print(a)
    ans+=a*base
    base*=2
  #  print(ans,a,k)
  ans=ans%MOD
print(ans)
  

### FIXED CODE ###

N=int(input())
MOD=10**9+7
L=60
ls=[int(s) for s in input().split()]
bi_ls=[0 for _ in range(L)]
for i in range(N):
  for j in range(L):
    if (2**j)&ls[i]>0:
      bi_ls[j]+=1    
ans=0
base=1
for j in range(L):
  ans=(ans+bi_ls[j]*(N-bi_ls[j])*base)%MOD
  base*=2%MOD
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]

ans = float("inf")

for i in range(N):
	ans = min(ans, abs(sum(A[:i])-sum(A[i:])))

print(ans)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]

l = sum(A)
ans = float("inf")
t = 0

for i in range(N-1):
	t += A[i]
	ans = min(ans,abs(l-2*t))
	#print("t,ans",t,ans)

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

import math
n=int(input())
A=[int(i) for i in input().split()]
A.sort(reverse=True)
B=[]
for a in A:
  B.append(a)
count=0
for i in range(n):
  cur=A[i]
  if cur in B:
    B=B[1:]
    k=int(math.log2(cur))+1
    pair=2**k-cur
    if pair in B:
      B.remove(pair)
      count+=1
print(count)


### FIXED CODE ###

import bisect
import collections
def f(n):
  return n.bit_length()
n=int(input())
A=[int(i) for i in input().split()]
D=dict(collections.Counter(A))
C=sorted(list(D.keys()))
ans=0
for i in range(len(C)):
  pair=2**f(C[-(i+1)])-C[-(i+1)]
  k=bisect.bisect_left(C,pair)
  if C[k]==pair:
    if k==len(C)-(i+1):
      ans+=D[pair]//2
      D[pair]%=2
    else:
      aa=min(D[pair],D[C[-(i+1)]])
      ans+=aa
      D[pair]-=aa
      D[C[-(i+1)]]-=aa
print(ans)
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())
xyz = {i:[] for i in range(1, n+1)}
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append((x, y, z))
    xyz[y].append((y, x, z))

connects = [0]*(n+1)
group = 1
for i in range(1, n+1):
    if connects[i] > 0:
        continue
    if len(xyz[i]) == 0:
        connects[i] = group
        group += 1
        continue

    que = deque(xyz[i])
    connects[i] = group
    while len(que) > 0:
        x, y, z = que.popleft()
        connects[y] = group
        for xn, yn, zn in xyz[y]:
            if connects[yn] > 0:
                pass
            else:
                que.append((xn, yn, zn))
    group += 1
    
# print(connects)
print(max(connects))


### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
xyz = {i:[] for i in range(1, n+1)}
for _ in range(m):
    x, y, z = map(int, input().split())
    xyz[x].append((x, y, z))
    xyz[y].append((y, x, z))

connects = [0]*(n+1)
group = 1
for i in range(1, n+1):
    if connects[i] > 0:
        continue
    if len(xyz[i]) == 0:
        connects[i] = group
        group += 1
        continue

    que = deque(xyz[i])
    connects[i] = group
    while len(que) > 0:
        x, y, z = que.popleft()
        connects[y] = group
        for xn, yn, zn in xyz[y]:
            if connects[yn] > 0:
                pass
            else:
                que.append((xn, yn, zn))
    group += 1
    
# print(connects)
print(max(connects))
### BUGGY CODE ###

N=int(input())

A=[]

for i in range(1,N+1):
  if N % i ==0:
    A.append(i)

base = int(len(A)/2)

print(A[base]-1 +A[base-1] -1)

### FIXED CODE ###

import math
 
N=int(input())

A=[]

for i in range(1,int(math.sqrt(N))+1):
  if N % i ==0:
    A.append(i)
    A.append(int(N/i))
    
A.sort()
base = int(len(A)/2)

print(A[base]-1 +A[base-1] -1)