Harryxun/stf_run huggingface dataset:
n = int(input())
a = list(map(int, input().split()))
s = [0 for i in range(n+1)]
sum = 0
for i in range(n):
    sum += a[i]
    s[i+1] = sum
s.sort()
ans = 0
for i in range(1,n+1):
    if s[i] == s[i-1]:
        j = i-1
        while s[i] == s[j]:
            ans += 1
            j -= 1
print(ans)

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n = I()
    a = LI()
    for i in range(n-1):
        a[i+1] += a[i]
    a.insert(0,0)
    f = defaultdict(lambda : 0)
    ans = 0
    for i in a:
        ans += f[i]
        f[i] += 1
    print(ans)
    return
#B
def B():

    return

#C
def C():

    return

#D
def D():

    return

#E
def E():

    return

#F
def F():

    return

#Solve
if __name__ == "__main__":
    A()
n=int(input())
s=input()
ans=0
x=[]
for i in range(n):
    if s[i]=='I':
        ans+=1
        x.append(ans)
    else:
        ans-=1
print(max(x))

### FIXED CODE ###

n = int(input())
s = input()
a = []
a.append(0)

for i in range(n):
    if s[i] == 'I':
        a.append(a[i]+1)
    else:
        a.append(a[i]-1)
print(max(a))
n, m = map(int, input().split())
s_li_ = []
c_li_ = []

for _ in range(m):
  s, c = map(int, input().split())
  s_li_.append(s)
  c_li_.append(c)

def func(n, s_li, c_li):
  if n==1:
    if (s_li[0]==1) and (c_li[0]==0):
      return 0
  
  for i in range(10**(n-1), 10**n):
    cnt = 0
    for s, c in zip(s_li, c_li):
      if str(i)[s-1] == str(c):
        cnt+=1
    if cnt==n:
      return i
    
  return -1

print(func(n, s_li_, c_li_))

### FIXED CODE ###

n, m = map(int, input().split())
s_li_ = []
c_li_ = []

for _ in range(m):
  s, c = map(int, input().split())
  s_li_.append(s)
  c_li_.append(c)

def func(n, m, s_li, c_li):
  if m==0:
    if n==1:
      return 0
    else:
      return 10**(n-1)
  
  if n==1:
    if (s_li[0]==1) & (c_li[0]==0):
      return 0
  
  for i in range(10**(n-1), 10**n):
    cnt = 0
    for s, c in zip(s_li, c_li):
      if str(i)[s-1] == str(c):
        cnt+=1
    if cnt==m:
      return i
    
  return -1

print(func(n, m, s_li_, c_li_))
import math
a,b,k =map(int, input().split())
c = math.gcd(a,b)
cnt = 0
for i in range(c, 0, -1):
    if a%i==0 and b%i==0:
        cnt +=1
    if cnt ==k:
        print(i)
        break

### FIXED CODE ###

a,b,k =map(int, input().split())
c = min(a, b)
cnt = 0
for i in range(c, 0, -1):
    if a%i==0 and b%i==0:
        cnt +=1
    if cnt ==k:
        print(i)
        break
import sys

n, m, r = [str(x) for x in sys.stdin.readline().split()]

for i in range(m):
	a = (n * (i + 1)) % m
	if a == r:
		print('YES')
		break
	print('NO')

### FIXED CODE ###

import sys

n, m, r = [int(x) for x in sys.stdin.readline().split()]
b = 0
for i in range(m):
	a = (n * (i + 1)) % m
	if a == r:
		b = 1
		break
if b == 1:
	print('YES')
else:
	print('NO')
def insertionSort(A,N):
  for i in range(N):
      j = i
      while (j > 0) and (A[j-1] > A[j]) :
          tmp = A[j-1]
          A[j-1] = A[j]
          A[j] = tmp
          j -= 1
      print(' '.join(map(str, A)))
  
N = input()
N = int(N)
A = input()
A = list(map(int, A.split()))
insertionSort(A,N)


### FIXED CODE ###

def insertionSort(A,N):
  for i in range(N):
      j = i
      while (j > 0) and (A[j-1] > A[j]) :
          tmp = A[j-1]
          A[j-1] = A[j]
          A[j] = tmp
          j -= 1
      print(' '.join(map(str, A)))
  
N = input()
N = int(N)
A = input()
A = list(map(int, A.split()))
insertionSort(A,N)
def bubbleSort(list_, n):
    list_ = list_[:]
    count = 0
    for i in xrange(n):
        for j in xrange(n-1, i, -1):
            if list_[j] < list_[j - 1]:
                list_[j], list_[j - 1] = list_[j - 1], list_[j]
                count += 1

    return list_

n = input()
nums = map(int, raw_input().split())
sorted_, count = bubbleSort(nums, n)
print sorted
print count

### FIXED CODE ###

def bubbleSort(list_, n):
    count = 0
    for i in xrange(n):
        for j in xrange(n-1, i, -1):
            if list_[j] < list_[j - 1]:
                list_[j], list_[j - 1] = list_[j - 1], list_[j]
                count += 1

    return count

n = input()
nums = map(int, raw_input().split())
count = bubbleSort(nums, n)
print ' '.join(map(str, nums))
print count
N=input()

if N%2==0:
  print(N/2)
  
else:
  print(N//2+1)

### FIXED CODE ###

N=int(input())

if N%2==0:
  print((N/2)/N)
  
else:
  print((N//2+1)/N)
a,b = map(int,input().split())

k = 50

m = []

for i in range(k):
    m.append(["#"]*2*k)
for i in range(k):
    m.append(["."]*2*k)

a , b -= 1

for i in range(0,k-1,2):
    for j in range(0,2*k,2):
        if a > 0:
            m[i][j] = "."
            a -= 1 
for i in range(k+1,2*k,2):
    for j in range(0,2*k,2):
        if b > 0:
            m[i][j] = "#"
            b -= 1  

print(2*k,2*k)


for i in m:
    print("".join[i])

### FIXED CODE ###

import sys,collections as cl,bisect as bs,math
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def onem():
    return int(input())
def s(x):
    a = []
    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):
    return " ".join(map(str,x))

a,b = m()

print(100,100)
aa = [["." for i in range(100)] for j in range(100)]
c = 0
for i in range(50):
    for j in range(100):
        aa[i][j] = "#"
a -= 1
b -= 1
k = 0
for i in range(100):
    if i <= 48:
        if k == 1:
            k = 0
            continue
        if a != 0:
            for j in range(100):
                if a == 0:
                    break
                if i//2 % 2 == 0:
                    if j % 2 == 0:
                        aa[i][j] = "."
                        a -= 1
                        k = 1
                else:
                    if j % 2 == 1:
                        aa[i][j] = "."
                        a -= 1
                        k = 1
    elif i >= 51:
        if k == 1:
            k = 0
            continue
        if b == 0:
            break
        else:
            for j in range(100):
                if b == 0:
                    break
                if i//2 % 2 == 0:
                    if j % 2 == 0:
                        aa[i][j] = "#"
                        b -= 1
                        k = 1
                else:
                    if j % 2 == 1:
                        aa[i][j] = "#"
                        b -= 1
                        k = 1
    else:
        k = 0

for i in range(100):
    print("".join(aa[i]))
import numpy as np

n, w = map(int, input().split())
wv = [list(map(int, input().split())) for i in range(n)]
table = np.zeros(w+1, dtype=np.int64)

for i in range(n):
    l = table[:-wv[i][0]]
    r = table[wv[i][0]:]
    np.maximum(l + wv[i][1], r, out = r)

print(table[w])

### FIXED CODE ###

import numpy as np

def main():
	N, W = map(int, input().split())
	dp = np.full(N * 1000 + 1, 10 ** 10, dtype=np.int64)
	dp[0] = 0
	for _ in range(N):
		w, v = map(int, input().split())
		np.minimum(dp[:-v] + w, dp[v:], out=dp[v:])
	print(((dp <= W) * np.arange(N * 1000 + 1)).max())

if __name__ == "__main__":
	main()
import heapq

max_v,m = input().split()
max_v = int(max_v)
m = int(m)

class Edge(object):
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost


edges = [[] for j in range(max_v)]
for i in range(max_v):
  a, b = input().split()
  a = int(a)
  b = int(b)
  edges[a-1].append(Edge(b-1,1))
  edges[b-1].append(Edge(a-1,1))

d = [float("inf")]*max_v
fire = [-1]*max_v
def dijkstra(s):
	h = []
	d[s] = 0
	heapq.heappush(h, [0,0])
	while(len(h) != 0):
		p = heapq.heappop(h)
		v = p[1]
		if d[v] < p[0]:continue
		for i in range(len(edges[v])):
			e = edges[v][i]
			if d[e.to] > d[v] + e.cost:
				d[e.to] = d[v] + e.cost
				heapq.heappush(h, [d[e.to], e.to])
				fire[e.to] = v
dijkstra(0)
if 2 <= fire.count(-1):
  print("No")
else:
  print("Yes")
  for i in range(max_v-1):
    print(d[i+1])

### FIXED CODE ###

import heapq

max_v,m = input().split()
max_v = int(max_v)
m = int(m)

class Edge(object):
	def __init__(self, to, cost):
		self.to = to
		self.cost = cost


edges = [[] for j in range(max_v)]
for i in range(m):
  a, b = input().split()
  a = int(a)
  b = int(b)
  edges[a-1].append(Edge(b-1,1))
  edges[b-1].append(Edge(a-1,1))

d = [float("inf")]*max_v
fire = [-1]*max_v
#fire = [[[]for j in range(max_v)] for i in range(max_v)]
def dijkstra(s):
	h = []
	d[s] = 0
	heapq.heappush(h, [0,0])
	while(len(h) != 0):
		p = heapq.heappop(h)
		v = p[1]
		if d[v] < p[0]:continue
		for i in range(len(edges[v])):
			e = edges[v][i]
			if d[e.to] > d[v] + e.cost:
				d[e.to] = d[v] + e.cost
				heapq.heappush(h, [d[e.to], e.to])
				fire[e.to] = v
dijkstra(0)
if 2 <= fire.count(-1):
  print("No")
else:
  print("Yes")
  for i in range(1, max_v):
    print(fire[i]+1)
import math

def lcm(x,y):
    return (x * y) // math.gcd(x, y)
def atwo(n,m,s,t):
    l=lcm(n,m)
    a=l/n
    b=l/m
    for i in range(n):
        for j in range(m):
            if a*i==b*j:
                if s[i]==t[j]:
                    pass
                else:
                    l=-1

    return l

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

### FIXED CODE ###

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

def lcm(x,y):
    return (x * y) // gcd(x, y)

def atwo(n,m,s,t):
    l=lcm(n,m)
    gc=gcd(n,m)
    if s[0::n//gc]==t[0::m//gc]:
        print(l)
        exit()
    else:
        print(-1)
        exit()

n,m=map(int,input().split())
print(atwo(n,m,input(),input()))
def solve():
    h, w = map(int,input().split())
    ch, cw = map(int,input().split())
    dh, dw = map(int,input().split())
    
    ch += 1
    cw += 1
    dh += 1
    dw += 1
    
    
    s = ["#"*(w+4)]
    s.append("#"*(w+4))
    for i in range(h):
        s.append("##" + input()[:-1] + "##")
    s.append("#"*(w+4))
    s.append("#"*(w+4))
    
    
    ans = [[-1]*(w+4) for _ in range(h+4)]
    for i in range(h+4):
        for j in range(w+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ans[ch][cw] = 0
    
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    move2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), \
             (-1, -2), (-1, -1), (-1, 0), (-1, 1), (-1, 2), \
             (0, -2), (0, -1), (0, 0), (0, 1), (0, 2), \
             (1, -2), (1, -1), (1, 0), (1, 1), (1, 2), \
             (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
        
    not_yet = [(ch, cw)]
    one_time = []
    
    while len(not_yet) > 0:
        x, y = not_yet.pop()
        one_time.append((x, y))
        for (p, q) in move:
            v1, v2 = x+p, y+q
            if ans[v1][v2] == -1:
                not_yet.append((v1, v2))
                ans[v1][v2] = ans[x][y]
                
        if len(not_yet) == 0:
            while len(one_time) > 0:
                x2, y2 = one_time.pop()
                for (v1, v2) in move2:
                    i, j = x2+v1, y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        not_yet.append((i, j))
    print(ans[dh][dw])
      
solve()

### FIXED CODE ###

from collections import deque


H,W = map(int,input().split())
Ch,Cw = map(int,input().split())
Dh,Dw = map(int,input().split())
S = [input() for i in range(H)]

dist = [[10**9+7] * W for _ in range(H)]
Ch = Ch-1
Cw = Cw-1
Dh = Dh-1
Dw = Dw-1

queue = deque()
queue.append((Ch,Cw))
queue2 = deque()
dist[Ch][Cw] = 0

walk = [[0,1],[1,0],[0,-1],[-1,0]]
    
while len(queue) > 0:
    while len(queue) > 0:
        h, w = queue.popleft()
        d = dist[h][w]
        flag = 0
        for vh,vw in walk:
            nh = h + vh
            nw = w + vw
            if 0 <= nh and nh < H and 0 <= nw and nw < W:
                if S[nh][nw] == '.':
                    if dist[nh][nw] > d:
                        dist[nh][nw] = d
                        queue.append([nh,nw])
                else:
                        flag += 1
        if flag:
            queue2.append([h,w])
            
    while len(queue2) > 0:
        h, w = queue2.popleft()
        for vh in range(-2,3):
            for vw in range(-2,3):
                nh = h + vh
                nw = w + vw
                if 0 <= nh and nh < H and 0 <= nw and nw < W:
                    if S[nh][nw] == '.' and dist[nh][nw] == 10**9+7:
                        dist[nh][nw] = dist[h][w] + 1
                        queue.append([nh,nw])
                
if dist[Dh][Dw] != 10**9+7:
    print(dist[Dh][Dw])
else:
    print(-1)
import numpy as np
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
def yaku(n):
    fct = factorize(n)
    y = divisorize(fct)
    ys = []
    for yy in y:
        ys.append(num(yy))
    ys.sort()
    return ys

n,m = list(map(int,input().split()))
y = yaku(m)
np.max(np.array(y)[np.array(y) <= m/n])

### FIXED CODE ###

import numpy as np
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
def yaku(n):
    fct = factorize(n)
    y = divisorize(fct)
    ys = []
    for yy in y:
        ys.append(num(yy))
    ys.sort()
    return ys

n,m = list(map(int,input().split()))
if n == 1 and m == 1:
    print(1)
else:
    y = yaku(m)
    print(np.max(np.array(y)[np.array(y) <= m/n]))
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

s = input()
t = input()
n = len(s)
m = len(t)
for i in range(m-1,n)[::-1]:
    if s[i] == t[-1] or s[i] == '?':
        cnt = 0
        flg = False
        while cnt < m:
            if s[i-cnt] == t[-(cnt+1)] or s[i-cnt] == '?':
                cnt += 1
                if cnt == m:
                    flg = True
            else:
                break

        if flg:
            break
if not flg:
    print('UNRESTORABLE')
    quit()
ans = ''
cnt2 = 0
for k in range(n):
    if i-cnt < k <= i:
        ans += t[cnt2]
        cnt2 += 1
    else:
        if s[k] == '?':
            ans += 'a'
        else:
            ans += s[k]
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
#ABC76 C

from copy import deepcopy
s = list(input())
t = list(input())

ns = len(s)
nt = len(t)
f1 = 0
for i in range(ns):
    if s[i] in t:
        ind = t.index(s[i])
        for j in range(i-ind,i-ind+nt):
            if j < ns:
                if s[j] == t[j-i+ind] or s[j] == '?':
                    continue
                else:
                    break
            else:
                break
        else:
            f1 = 1
            x = deepcopy(s)
            x[i-ind:i-ind+nt] = t
            break
f2 = 0
for i in range(ns)[::-1]:
    if s[i] == '?':
        for j in range(i,i+nt):
            if j < ns:
                if s[j] == t[j-i] or s[j] == '?':
                    continue
                else:
                    break
            else:
                break
        else:
            f2 = 1
            y = deepcopy(s)
            y[i:i+nt] = t
            break
if f1 & f2:
    for i in range(ns):
        if x[i] == '?':
            x[i] = 'a'
        if y[i] == '?':
            y[i] = 'a'
    x = ''.join(x)
    y = ''.join(y)
    ans = [x,y]
    ans.sort()
    print(ans[0])

elif f1 and not f2:
    for i in range(ns):
        if x[i] == '?':
            x[i] = 'a'
    x = ''.join(x)
    print(x)
elif not f1 and f2:
    for i in range(ns):
        if y[i] == '?':
            y[i] = 'a'
    y = ''.join(y)
    print(y)
else:
    print('UNRESTORABLE')
A
 
B


### FIXED CODE ###

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

ans = None

if A+B > 23:
  ans = A+B-24
else:
  ans = A+B
print(ans)
def solve(n, y):
    for man in range(0, n + 1):
        for gosen in range(0, n - man + 1):
            sen = n - man - gosen
            if 10000*man + gosen*5000 + sen*1000 == y and man + gosen + sen == n:
                print('{} {} {}'.format(man, gosen, sen))
                return 0

    print("-1 -1 -1")
    return 0            

#main
n = int(input())
y = int(input())
solve(n, y)




### FIXED CODE ###

def solve(n, y):
    for man in range(n + 1):
        for gosen in range(n - man + 1):
            sen = n - man - gosen
            if 10000*man + gosen*5000 + sen*1000 == y and man + gosen + sen == n:
                print('{} {} {}'.format(man, gosen, sen))
                return
    print("-1 -1 -1")
    return            

#main
n, y = map(int, raw_input().split())
solve(n, y)
import sys
input = sys.stdin.readline

MOD = 1_000_000_007


def main():
    N, M = map(int, input().split())
    memo = [0] * (N + 1)
    a = [0] * M

    memo[0] = 0
    memo[1] = 1
    memo[2] = 2
    for i in range(3, N+1):
        memo[i] = memo[i-1] + memo[i-2]

    # print(memo)
    ans = 1

    for i in range(M):
        a[i] = int(input())

        if i != 0 and abs(a[i] - a[i-1]) == 1:
            print(0)
            return

        if a[i] == 1:
            ans *= 1
        elif i == 0:
            ans *= memo[a[i] - 1]
            ans %= MOD
            # print(a[i], ans, a[i] - 1)
        else:
            ans *= memo[a[i] - a[i-1] - 2]
            ans %= MOD
            # print(a[i], ans, a[i] - a[i-1] - 2)

    ans *= memo[N - a[M-1] - 1]
    ans %= MOD
    # print(ans, N - a[M-1] - 1)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD = 10 ** 9 + 7


def main():
    N, M = map(int, input().split())
    memo = [0] * max((N + 1), 10)
    a = [0] * M

    memo[0] = 1
    memo[1] = 1
    memo[2] = 2
    for i in range(3, max(N+1, 10)):
        memo[i] = memo[i-1] + memo[i-2]

    # print(memo)
    ans = 1

    for i in range(M):
        a[i] = int(input())

        if i != 0 and abs(a[i] - a[i-1]) == 1:
            print(0)
            return

        if a[i] == 1:
            ans *= 1
        elif i == 0:
            ans *= memo[a[i] - 1]
            ans %= MOD
            # print(a[i], ans, a[i] - 1)
        else:
            ans *= memo[a[i] - a[i-1] - 2]
            ans %= MOD
            # print(a[i], ans, a[i] - a[i-1] - 2)

    if M == 0:
        ans *= memo[N]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)
    else:
        ans *= memo[N - a[M-1] - 1]
        ans %= MOD
        # print(ans, N - a[M-1] - 1)
        print(ans)


if __name__ == '__main__':
    main()
import itertools,math,bisect,pprint,sys
n, a, b = map(int, raw_input().split())
v = sorted(map(int, raw_input().split()))[::-1]
res1 = sum(v[:a])*1.0/a
print res1
res2 = 0
def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)
if a==v[:a].count(v[a]):
    res2 = 0
    for i in range(a,b):
        res2 += nCr(v.count(v[i]),i)
else:
    print nCr(v.count(v[a]),v[:a].count(v[a]))

### FIXED CODE ###

import itertools,math,bisect,pprint,sys
n, a, b = map(int, raw_input().split())
v = sorted(map(int, raw_input().split()))[::-1]
res1 = sum(v[:a])*1.0/a
print '{0:.6f}'.format(res1)
res2 = 0
def nCr(n,r):
    f = math.factorial
    return f(n) / f(r) / f(n-r)
if a==v[:a].count(v[a-1]):
    res2 = 0
    for i in range(a,b+1):
        if i <= v.count(v[a-1]):
            res2 += nCr(v.count(v[a-1]),i)
    print res2
else:
    print nCr(v.count(v[a-1]),v[:a].count(v[a-1]))
import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
ba = np.array(list(format(i,'b').zfill(60)) for i in a])
mod = 10**9+7

"""
#2^iをmodで割った余りを出しておく
twos = [1]
for i in range(1,60):
    twos.append((twos[i-1]*2)%mod)

#各baのbitごとに0の個数を求める
c0 = np.sum(ba, axis=1)
"""

#答えは各bitごとの(0の数)*(1の数)より求まる
ans = 0
for i in range(60):
    ans += (((c0[59-i]*(n-c0[59-i]))%mod)*twos[i])%mod

ans %= mod
print(int(ans))


### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7

twos = 1
ans = 0
for i in range(0,60):
    cou1 = np.count_nonzero((a >> i) & 1)
    ans += (cou1*(n-cou1)*twos)%mod
    twos = (twos*2)%mod

ans %= mod
print(ans)
s = input()
k = int(input())
n = len(s)
# print(s,k,n)

c = set()
for i in range(n-1):
    for j in range(i+1, n+1):
        c.add(s[i:j])

c=list(c)
# print(c)
c.sort()
# print(c)

if len(c) > 0: print(c[k-1])
else: print(s)





### FIXED CODE ###

s = input()
k = int(input())
n = len(s)

# print('s',s,'k',k)
c = set()
for i in range(n):
    # print(s[i:i+5])
    t = s[i:i+5]
    for j in range(1,5+1):
        # print(t[:j])
        c.add(t[:j])

c = list(c)
c.sort()
# print(*c,sep='\n')
print(c[k-1])
n = int(input())
a = list(map(int,input().split()))
ans1 = max(a)
diff = min(ans1//2, ans1//2 + 1)
ans2 = ans1
for x in a:
  if x == ans1:
      continue
  d = min(abs(ans1//2 - x), abs(ans1//2 + 1 - x))
  if d <= diff:
    diff = d
    ans2 = x
print('{} {}'.format(ans1, ans2)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans1 = max(a)
diff = min(ans1//2, ans1//2 + 1)
ans2 = ans1
for x in a:
  if x == ans1:
    continue
  d = min(abs(ans1//2 - x), abs(ans1//2 + 1 - x))
  if d <= diff:
    diff = d
    ans2 = x
print('{} {}'.format(ans1, ans2))