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

def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return
def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l, i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    for ans in ANS:
        print(ans)    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

def main():
  N,Q=map( int, input().split())
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=map( int, input().split())
    LRI.append((r,l,i))
  LRI.sort(key=lambda x:x[0])
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

a,b,n = map(int,input().split())
n = 0
for x in range(10**12):
    c = int(a*x/b)
    d = int(x/b)
    if c - a*d >= n:
        n = c-d
print(n)

### FIXED CODE ###

a,b,n = map(int,input().split())
if b <= n:
    k = b-1
else:
    k = n
m = int(k*a/b) - a*int(k/b)
print(m)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
point = 1
for i in range(N):
    if i < K:
        point = point * A[i]
    else:
        pointed = point
        point = point * A[i] // A[i-K]
        if point > pointed:
            print('Yes')
        else:
            print('No')

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(N):
    if i < K:
        continue
    if A[i] > A[i-K]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
def gcd(a,b):
  if b==0:
    return a
  else:
  	return gcd(b, a%b)

def gcd_list(X):
  dmy=gcd(X[0],X[1])
  dmy=X[0]*X[1]
  for i in range(len(X)):
    dmy=gcd(dmy,X[i])
  return dmy
 
if N==2:
  print(max(A))
else:
  R=0
  for i in range(N):
    C=A[:i]
    C.extend(A[i+1:])
    #R.append(gcd_list(C))
    #R[i]=gcd_list(C)
    R=max(R,gcd_list(C))
 
  #print(int(max(R)))
  print(int(R))

### FIXED CODE ###

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

N = int(input())
A = [i for i in map(int,input().split())]
L = [0]
R = [0]
for i in range(N):
    L.append(gcd(L[-1],A[i]))
for i in range(N-1,-1,-1):
    R.append(gcd(R[-1],A[i]))
R.reverse()
g = []
for i in range(N):
    g.append(gcd(L[i],R[i+1]))
print(max(g))
### BUGGY CODE ###

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

 #最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

N=int(input())
A=list(map(int,input().split()))
a_lcm=A[0]

for i in range(1,N):
    a_lcm=lcm(a_lcm,A[i])

result=0
for i in range(N):
    result+=(a_lcm//A[i])%1000000007
print(result%1000000007)

### FIXED CODE ###

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

 #最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

N=int(input())
A=list(map(int,input().split()))
a_lcm=A[0]
Mod=10**9+7

for i in range(1,N):
    a_lcm=lcm(a_lcm,A[i])

a_lcm%=Mod

result=0
for i in range(N):
    result+=a_lcm*pow(A[i],Mod-2,Mod)
print(result%1000000007)
### BUGGY CODE ###

from sys import stdin
from itertools import accumulate
q = int(stdin.readline().rstrip())
l_r = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
max_n = 0
for s in l_r:
    max_n = max(s[1], max_n)
# print(max_n)
# print(l_r)

a = [i for i in range(max_n+1)]

def isPrime(num):
    if num == 0 or num == 1:
        return False
    ans = True
    for i in range(2,int(num/2)+1):
        if num % i == 0:
            ans = False
            break
    return ans

b = [1 if isPrime(x) else 0 for x in a]
# print(b)
c = [1 if x == 1 and b[int((i+1)/2)] == 1 else 0 for i,x in enumerate(b)] 
# print(c)
s = list(accumulate(c))
# print(len(s))

for i in range(q):
    print(s[l_r[i][1]]-s[l_r[i][0]-1])

### FIXED CODE ###

from sys import stdin
from itertools import accumulate
q = int(stdin.readline().rstrip())
l_r = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]
max_n = 0
for s in l_r:
    max_n = max(s[1], max_n)
# print(max_n)
# print(l_r)

a = [i for i in range(max_n+1)]

def isPrime(num):
    if num == 0 or num == 1:
        return False
    ans = True
    for i in range(2,int(num/2)+1):
        if num % i == 0:
            ans = False
            break
    return ans
b = [1] * (max_n+1)
b[0] = 0
b[1] = 0
for i in range(2,max_n+1):
    if b[i]:
        j = i*2
        while j <= max_n:
            b[j] = 0
            j += i
# print(b)
c = [1 if x == 1 and b[int((i+1)/2)] == 1 else 0 for i,x in enumerate(b)] 
# print(c)
s = list(accumulate(c))
# print(len(s))

for i in range(q):
    print(s[l_r[i][1]]-s[l_r[i][0]-1])
### BUGGY CODE ###

n,k = map(int,input().split())
p=list(map(int,input().split()))
a=0
for i in range(n):
  if sum(p[i:i+k])>a:
    a=sum(p[i:i+k])
print((a+k)/2)

### FIXED CODE ###

n,k=map(int, input().split())
p=list(map(int, input().split()))
num=sum(p[0:k])
ans=num
for i in range(n-k):
  num=num-p[i]+p[i+k]
  ans=max(ans,num)
print((ans+k)/2)
### BUGGY CODE ###

import re

n = int(input())

s = input()

l = []

for i in range(len(s)):
    l.append(s[i])


for h in range(len(l)-1):
 
    if l[h] == l[h+1]:
        l[h] = "red"

while "red" in l :
    l.remove("red")  #全ての"red"を削除します。


print(len(l))



### FIXED CODE ###



n = int(input())

s = input()


count = 1



for h in range(len(s)-1):
 
    if s[h] != s[h+1]:
        count += 1

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

nm = list(map(int,input().split()))
n = nm[0]
m = nm[1]
a = []
b = []
for i in range(0, m):
    ab = list(map(int,input().split()))
    a.append(ab[0])
    b.append(ab[1])
signs = [0]*(n+1)
signs[1]=-1
now = [1]
nexx = []
while True:
    for i in now:
        for j in range(0,m):
            if a[j] == i:
                if signs[b[j]] == 0:
                    signs[b[j]] = i
                    nexx.append(b[j])
            elif b[j] == i:
                if signs[a[j]] == 0:
                    signs[a[j]] = i
                    nexx.append(a[j])
    now=nexx.copy()
    if len(nexx)==0:
        break
    nexx = []
flag = 0
for i in range(2, n+1):
    if signs[i]==0:
        print("No")
        flag = 1
        break
if flag == 0:
    print("Yes")
    for k in range(2,n+1):
        print(signs[k])



### FIXED CODE ###

n, m = map(int,input().split())
graph = {}
for i in range(0, m):
    am, bm = map(int, input().split())
    if am not in graph:
        graph[am] = [bm]
    else:
        graph[am].append(bm)
    if bm not in graph:
        graph[bm] = [am]
    else:
        graph[bm].append(am)
signs = {1:0}
current = [1]
i = 0
while True:
    flag = 0
    for j in graph[current[i]]:
        if j not in signs:
            signs[j] = current[i]
            current.append(j)
            flag = 1
    i+=1
    if flag == 0 and i == len(current):
        break
    
if i == n:
    print("Yes")
    for x in range(2, n+1):
        print(signs[x])
else:
    print("No")
### BUGGY CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()

a.sort()

aa = s(a)

ans = 0

for i in range(len(aa)):
	co = 0
	f = 0
	for j in range(i):
		if aa[i][0] >= aa[j][0] * 2:
			if aa[i][0] // aa[j][0] == aa[i][0] / aa[j][0]:
				f = 1
		else:
			break
	if aa[i][1] != 1:
		f = 1
	if not f:
		ans += 1



print(ans)


### FIXED CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
	return list(map(int,input().split()))
def m(): #複数文字
	return map(int,input().split())
def onem(): #Nとかの取得
	return int(input())
def s(x): #圧縮
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): #listをスペースごとに分ける
	return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
	return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

n = onem()

a = l()

a.sort()

aa = s(a)

ans = 0
dp = [0 for i in range(10**6+1)]
for i in range(len(aa)):
	f = 0
	if aa[i][1] != 1:
		f = 1
	elif dp[aa[i][0]] != 0:
		f = 1
	for _ in range(aa[i][0],10**6+1,aa[i][0]):
		dp[_] = 1
	if not f:
		ans += 1



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

def solve(n, ga, sa, ba, gb, sb, bb):
    gd, sd, bd = gb - ga, sb - sa, bb - ba

    if bd <= 0:
        if sd <= 0:
            if gd <= 0:
                return n
            return n + n // ga * gd
        return max(n + g * gd + (n - g * ga) // sa * sd for g in range(n // ga + 1))
    if sd <= 0:
        if gd <= 0:
            return n + n // ba * bd
        return max(n + g * gd + (n - g * ga) // ba * bd for g in range(n // ga + 1))
    if gd <= 0:
        return max(n + s * sd + (n - s * sa) // ba * bd for s in range(n // sa + 1))
    return max(n + g * gd + s * sd + (n - g * ga - s * sa) // ba * bd
               for g in range(n // ga + 1) for s in range((n - g * ga) // sa + 1))


n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))
n2 = solve(n, ga, sa, ba, gb, sb, bb)
n3 = solve(n2, gb, sb, bb, ga, sa, ba)
print(n3)


### FIXED CODE ###

def solve(n, ga, sa, ba, gb, sb, bb):
    ans = n
    for g in range(1 if ga >= gb else n // ga + 1):
        n2 = n - g * ga
        tmp1 = g * gb
        if ba >= bb:
            s = n2 // sa
            ans = max(ans, n2 + tmp1, n2 - s * sa + tmp1 + s * sb)
        elif sa >= sb:
            b = n2 // ba
            ans = max(ans, n2 + tmp1, n2 - b * ba + tmp1 + b * bb)
        else:
            for s in range(n2 // sa + 1):
                b = (n2 - s * sa) // ba
                ans = max(ans, n2 - s * sa - b * ba + tmp1 + s * sb + b * bb)
    return ans


n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))
n2 = solve(n, ga, sa, ba, gb, sb, bb)
n3 = solve(n2, gb, sb, bb, ga, sa, ba)
print(n3)
### BUGGY CODE ###

N,M = map(int,input().split())
A = M//N
L = []
for i in range(1,A+1):
  if (M%i == 0):
    L.append(i)
print(L[len(L)-1])

### FIXED CODE ###

import math

N,M = map(int,input().split())
A = M//N
L = []
for i in range(1,int(math.sqrt(M))+1):
  if (M%i == 0 and i <= A):
    L.append(i)
    if (M//i <= A):
      L.append(M//i)
print(max(L))
### BUGGY CODE ###

from collections import deque
H, W, M = map(int, input().split())
grid = [[0 for _ in range(W)] for _ in range(H)]
counth = deque([0 for k in range(H)])
countw = deque([0 for k in range(W)])
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  grid[h][w] = 1
  counth[h] += 1 
  countw[w] += 1

maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = deque([])
k = 0
while len(counth) > 0:
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)
  k += 1
k = 0
while len(countw) > 0:
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)
  k += 1
ans = maxh + maxw - 1
while len(index_h) > 0:
  h = index_h.pop()
  while len(index_w) > 0:
    w = index_w.pop()
    if grid[h][w] == 0:
      ans += 1
      break
  else:
    continue
  break
print(ans)

### FIXED CODE ###

from collections import deque
H, W, M = map(int, input().split())
bomb = []
counth = [0 for k in range(H)]
countw = [0 for k in range(W)]
for k in range(M):
  h, w = map(int, input().split())
  h -= 1
  w -= 1
  bomb.append(h+ w*H)
  counth[h] += 1 
  countw[w] += 1
counth = deque(counth)
countw = deque(countw)

def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) //2
        guess = list[mid]
        if guess == item:
            #return mid
            return True
        if guess > item:
            high = mid -1
        else:
            low = mid + 1

    #return None
    return False


maxh = max(counth)
maxw = max(countw)
index_h = deque([])
index_w = []
for k in range(H):
  h = counth.popleft()
  if h == maxh:
    index_h.append(k)

for k in range(W):
  w = countw.popleft()
  if w == maxw:
    index_w.append(k)

ans = maxh + maxw - 1
lenh = len(index_h)
lenw = len(index_w)


if lenh*lenw > M:
  ans += 1
else:
  bomb.sort()
  kouho = []
  for i in range(lenh):
    h = index_h.pop()
    for j in range(lenw):
      w = index_w[j]
      kouho.append(h+ H*w)
  for K in kouho:
    if binary_search(bomb, K):
      continue
    else:
      ans += 1
      break
    
print(ans)
### BUGGY CODE ###

n=int(input())
a=[int(j) for j in input().split()]
from collections import Counter
c=Counter(a)
l=c.most_common()
ll=[]
for i,j in l:
    ll.append(-j)

import heapq
import copy
for k in range(1,1+n):
    if k==1:
        print(n)
    else:
        ans=0
        q=copy.deepcopy(ll)
        heapq.heapify(q)
        while True:
            if len(q)<k:
                break
            t=[]
            for i in range(k):
                t.append(-heapq.heappop(q))
            m=min(t)
            ans+=m
            for i in t:
                if i-m!=0:
                    heapq.heappush(q,-(i-m))
        print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline
n=int(input())
a=[int(j) for j in input().split()]
from collections import Counter
c=Counter(a)
l=c.most_common()
ll=[]
for i,j in l:
    ll.append(j)
ll.sort()
s=sum(ll)
rem=0
for k in range(1,n+1):
    rest=k-rem
    while ll and ll[-1]>s//rest:
        s-=ll[-1]
        ll.pop()
        rem+=1
        rest-=1
    print(s//rest)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

X, Y = map(int, input().split())

cnt_d1 = 0
cnt_d2 = 0

diff = Y - X
if diff == 0:
    if X % 3 != 0:
        print(0)
        exit()
    cnt_d1 = X // 3
    cnt_d2 = cnt_d1
elif diff > 0:
    Y -= 2 * diff
    X -= 1 * diff
    if X < 0 or X % 3 != 0:
        print(0)
        exit()

    cnt_d1 = X // 3
    cnt_d2 = diff + X // 3
else:
    diff = - diff
    X -= 2 * diff
    Y -= 1 * diff
    if X < 0 or X % 3 != 0:
        print(0)
        exit()

    cnt_d1 = diff + X // 3
    cnt_d2 = X // 3

MOD = 10**9 + 7
fact = [1]
fact_inv = [1]
for i in range(cnt_d1+cnt_d2 + 10):
    new_fact = fact[-1]*(i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD-2, MOD))


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] % mod


print(mod_comb_k(cnt_d1+cnt_d2, cnt_d1, MOD))

'''
dp = np.array([[0] * (Y + 1) for _ in range(X + 1)], dtype=np.int64)
#dp = [np.zeros(Y+1, np.int64) for _ in range(X+1)]
print(dp)

for i in range(X):
    if i > 0:
        dp[i] = dp[i]
'''


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

X, Y = map(int, input().split())

cnt_d1 = 0
cnt_d2 = 0

diff = Y - X
if diff == 0:
    if X % 3 != 0:
        print(0)
        exit()
    cnt_d1 = X // 3
    cnt_d2 = cnt_d1
elif diff > 0:
    Y -= 2 * diff
    X -= 1 * diff
    if X < 0 or X % 3 != 0:
        print(0)
        exit()

    cnt_d1 = X // 3
    cnt_d2 = diff + X // 3
else:
    diff = - diff
    X -= 2 * diff
    Y -= 1 * diff
    if X < 0 or X % 3 != 0:
        print(0)
        exit()

    cnt_d1 = diff + X // 3
    cnt_d2 = X // 3

MOD = 10**9 + 7
fact = [1]
fact_inv = [1]
for i in range(cnt_d1+cnt_d2 + 10):
    new_fact = fact[-1]*(i+1) % MOD
    fact.append(new_fact)
    fact_inv.append(pow(new_fact, MOD-2, MOD))


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] % mod


print(mod_comb_k(cnt_d1+cnt_d2, cnt_d1, MOD))

'''
dp = np.array([[0] * (Y + 1) for _ in range(X + 1)], dtype=np.int64)
#dp = [np.zeros(Y+1, np.int64) for _ in range(X+1)]
print(dp)

for i in range(X):
    if i > 0:
        dp[i] = dp[i]
'''
### BUGGY CODE ###

from collections import deque as dq
N, M = map(int, input().split())
ab = []
c = []
inf = 10 ** 10
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
#print(ab, c)
Q = dq([])
Q.append((0, 0))
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  temp = i ^ 0
  temp2 = 0
  for k in range(ab[j][1]):
    t = 2 ** (c[j][k] - 1)
    temp2 = temp2 | t
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = min(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = min(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = min(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])



### FIXED CODE ###

from collections import deque as dq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = []
c = []
inf = 2 << 31
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
def less(a, b):
  if a > b:
    return b
  else:
    return a
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = [[0] * M for _ in range(2 ** 12)]
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if vis[i][j] == 1:
    continue
  vis[i][j] = 1
  temp = i ^ 0
  temp2 = cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = less(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = less(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])
### BUGGY CODE ###

from itertools import combinations

N = int(input())
A_list = tuple(map(int, input().split(' ')))

# print(N)
# print(A_list)

ret = 0
# 重複なしの組み合わせごとに積を出し、その和
for comb in combinations(A_list, 2):
  # print(comb)
  ret += comb[0] * comb[1]
  if ret > 1000000007:
    ret = ret % 1000000007
  
print(ret % 1000000007)

### FIXED CODE ###

N = int(input())
A_list = tuple(map(int, input().split(' ')))

# print(N)
# print(A_list)

ret = 0
now_sum = sum(A_list)
# print("スタート{}".format(now_sum))

for i in range(len(A_list)):
  now_sum -= A_list[i]
  multiple_base = A_list[i]
  # print('now_sumから{0}を引いて{1}'.format(A_list[i], now_sum))
  before_total = 0
  # print("before_totalは{0}, multiple_baseは{1}, 掛け算で{2}".format(multiple_base, before_total, multiple_base * before_total))
  ret += multiple_base * now_sum
  
print(ret % 1000000007)
### BUGGY CODE ###

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

H = []

def func(L):
    result = 0
    for i in range(len(L)-1):
        result += L[i+1] - L[i]
    return result


for n in range(N):
    H.append(int(input()))

H.sort()

R = [func(H[i:i+K]) for i in range(N+1-K)]

print(min(R))


### FIXED CODE ###

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

H = [int(input()) for n in range(N)]

H.sort()

R = [H[i+K-1] - H[i] for i in range(N+1-K)]

print(min(R))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    A = lmis()
    maxA = max(A)
    ans = 0
    for i in count():
        b = 1<<i
        if b > maxA:
            break
        S1 = sum(bool(a & b) for a in A)
        S0 = N - S1
        ans += (S1*S0) * (b%N1097)
        ans %= N1097
    print(ans)

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
from itertools import count
from functools import lru_cache
from collections import defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    S1 = [0] * 100
    for a in mis():
        b = 1
        for i in count():
            if b > a:
                break
            if a & b:
                S1[i] += 1
            b <<= 1
    ans = 0
    b = 1
    for i in range(len(S1)):
        s1 = S1[i]
        s0 = N - s1
        ans += (s1*s0) * (b%N1097)
        ans %= N1097
        b <<= 1

    print(ans)




main()
### BUGGY CODE ###

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

for i, value in enumerate(a):
    cnt = 0
    for j in range(i, len(a)):
        if a[j] == i+1:
            cnt += 1
    print(cnt)
print('0')


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*len(a)

for i, value in enumerate(a):
    b[value-1] += 1

for j in b:
    print(j) 

print('0')