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

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

nm_list = [bin(x)[2:][::-1] for x in nums]
lmax = len(nums)

def syakutori():
    ans = 0
    bits = [0]*21
    r = 0
    l = 0
    flag = True
    #尺取り法をする
    while((l < lmax) or (not flag)):
        if not flag:
            #print("a", l, r, bits)
            for i, b in enumerate(nm_list[r]):
                bits[i] -= int(b)
            r += 1
            flag = max(bits) <= 1
            if flag:
                ans += (l - r)

        #rを伸ばす(ついでに数え上げる)
        else:
            #print("ans", l, r, bits)
            for i, b in enumerate(nm_list[l]):
                bits[i] += int(b)
            flag = max(bits) <= 1
            l += 1
            if flag:
                ans += (l - r)

    return ans


print(syakutori())


### FIXED CODE ###

import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def solve():
    n = getN()
    lis = getList()
    xo, su = 0, 0
    ans = 0
    l, r = 0, 0
    forward = True
    while True:
        # print(l, r, ans, xo, su)
        if r == n:
            print(ans)
            return
        if forward:
            xo = xo^lis[r]
            su += lis[r]
            if xo == su:

                ans += r - l + 1
                r += 1
            else:
                forward = False
        else:
            xo = xo^lis[l]
            su -= lis[l]
            if xo == su:
                forward = True
                ans += r - l
                r += 1
                l += 1
            else:
                l += 1

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()
### BUGGY CODE ###

import re

n,q = map(int,input().split())
s = input()
lr = []
for i in range(q): lr.append(list(map(int, input().split())))
for i in lr: print(len(re.findall('AC', s[i[0]-1:i[1]])))

### FIXED CODE ###

import itertools
n,q = map(int,input().split())
s = input()
lr = []
for i in range(q): lr.append(list(map(int, input().split())))
ac = [1 if i!=0 and 'AC'==s[i-1:i+1] else 0 for i in range(0,len(s))]
acc = list(itertools.accumulate(ac))
for i in lr: print(acc[i[1]-1]-acc[i[0]-1])
### BUGGY CODE ###

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

for i in range(n):
    total = 0
    for j in range(i, n):
        total += lst[j]
        if total%m==0:
            ans += 1
print(ans)

### FIXED CODE ###

from collections import Counter
import numpy as np
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result
n, m = map(int, input().split())
lst = list(map(int, input().split()))
blst = [0]
total = 0
for i in range(n):
    total += lst[i]
    blst.append(total)
modblst = np.array(blst)%m
count = Counter(modblst)

ans = 0
for val in count.values():
    if val == 1:
        continue
    ans += cmb(val, 2)
print(ans)
### BUGGY CODE ###

import math
import operator as op
from functools import reduce


def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom


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

total = 0

for i in range(n-m+1):
    p = n - i - 1
    q = m - 1

    c = ncr(p, q)

    total -= c * a[i]
    total += c * a[-1-i]

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


### FIXED CODE ###

n, k = map(int, input().split())
a = sorted(list(map(int, input().split())))
mod = 10**9 + 7

f = [1, 1]
for i in range(2, n):
    f.append((f[i-1] * i) % mod)

total = 0
for i in range(n - k + 1):
    p = n - i - 1
    q = k - 1

    c = f[p] * pow(f[p-q], mod-2, mod) * pow(f[q], mod-2, mod) % mod
    total += c * (a[-1-i] - a[i])
    total = total % mod

print(total)
### 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):
            a, b, c = l[i], l[j], l[k]
            if a < b+c and b < c+a and c < a+b:
                ans += 1

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int, input().split()))
l.sort()
l_copy = l.copy()
l_copy = l_copy[::-1]

ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        rest = l_copy[i] - l_copy[j]
        ind = bisect.bisect_right(l, rest)
        ind = n - ind - 1
        if ind <= j:
            break
        else:
            ans += ind - j

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

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

for i in range(N) :
	print(A.count(i+1))

### FIXED CODE ###

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

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

for i in range(N) :
	print(A_cnt[i])
### BUGGY CODE ###

import itertools

n,m,l=map(int,input().split())
arr=list(map(int,input().split()))
d=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
  u,v,w=map(int,input().split())
  d[u-1][v-1]=w
  d[v-1][u-1]=w
for i in range(n):
  d[i][i]=0
for i in range(n):
  for j in range(n):
    for k in range(n):
      if d[j][k]>=d[j][i]+d[i][k]:
        d[j][k]=d[j][i]+d[i][k]
c=list(itertools.permutations(arr,min(8,l)))
ans=10**10
for i in c:
  tmp=0
  for j in range(min(8,l)-1):
    tmp+=d[i[j]-1][i[j+1]-1]
  ans=min(tmp,ans)
print(ans)

### FIXED CODE ###

import itertools
from scipy.sparse.csgraph import floyd_warshall

n,m,l=map(int,input().split())
arr=list(map(int,input().split()))
d=[[10**10 for i in range(n)] for j in range(n)]
for i in range(m):
  u,v,w=map(int,input().split())
  d[u-1][v-1]=w
  d[v-1][u-1]=w
for i in range(n):
  d[i][i]=0
d=floyd_warshall(d,directed=False)
c=list(itertools.permutations(arr,min(8,l)))
ans=10**10
for i in c:
  tmp=0
  for j in range(min(8,l)-1):
    tmp+=d[i[j]-1][i[j+1]-1]
  ans=min(tmp,ans)
print(int(ans))
### BUGGY CODE ###

n, m, q = map(int,input().split())
query = []
for i in range(q):
    query.append(list(map(int, input().split())))

#print(query)

import itertools
cnbr = []  #組み合わせ
for i in range(m+1):
    for j in itertools.combinations_with_replacement(range(m), n):
        cnbr.append(j)

#print(cnbr)
points = [0] * len(cnbr)

for _ in range(len(cnbr)):
    for a,b,c,d in query:
        if cnbr[_][b - 1] - cnbr[_][a - 1] == c:
            points[_] += d

print(max(points))

### FIXED CODE ###

N, M, Q = map(int, input().split())  #数字
Q = [list(map(int, input().split())) for i in range(Q)]  #数字複数列、複数行

A = []
for i in range(1,M+1):
    A.append(i)

B = []
import itertools
for i in itertools.combinations_with_replacement(A,N):
    B.append(i)

C = []
for i in range(len(B)):
    score = 0
    for j in range(len(Q)):
        if B[i][Q[j][1]-1] - B[i][Q[j][0]-1] == Q[j][2]:
            score += Q[j][3]
        C.append(score)

print(max(C))
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
aa=[]
for i in range(n):
    ans=0
    for j in a:
        if j!=a[i]:
            ans^=j
    aa.append(ans)
    ans=0
print(" ".join(map(str,aa)))

### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
aa=[]
ans=0
for i in a:
    ans^=i
anss=int(ans)
for i in range(n):
    anss^=a[i]
    aa.append(anss)
    anss=int(ans)
print(" ".join(map(str,aa)))
### BUGGY CODE ###

import collections

def cmb(n):
    return int(n*(n-1)/2)

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

c = collections.Counter(lis)
dic = {}

for key, value in c.items():
    dic[key] = cmb(value)

for i in range(n):
    ans = sum(list(dic.values()))
    ans -= dic[lis[i]]
    
    ans += cmb(c[lis[i]] -1)
    
    print(ans)

### FIXED CODE ###


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

ban = [0] * n

tmp = 0
for i in lis:
    ban[i-1] += 1

for i in ban:
    tmp += i*(i-1)//2
    
for i in lis:
    print(tmp+(1-ban[i-1]))
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def solve():
    N = I()
    A = III()
    B = III()

    first_use = []
    second_use = []
    for i in range(3):
        if A[i]<B[i]:
            first_use.append(i)
        if A[i]>B[i]:
            second_use.append(i)

    def change(n,A,B,use_index):
        dp = [(n-i) for i in range(n+1)]
        count = 0
        for i in range(n+1):
            for j in use_index:
                if i-A[j]>=0:
                    dp[i] = max(dp[i-A[j]]+B[j]-A[j],dp[i])
            count = max(count,dp[i])
        return count

    count1 = change(N,A,B,first_use)
    count2 = change(count1,B,A,second_use)

    print(count2)

solve()

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

def solve():
    N = I()
    A = III()
    B = III()

    first_use = []
    second_use = []
    for i in range(3):
        if A[i]<B[i]:
            first_use.append(i)
        if A[i]>B[i]:
            second_use.append(i)

    def change(n,A,B,use_index):
        dp = [n]*(n+1)
        for i in range(n+1):
            for j in use_index:
                if i-A[j]>=0:
                    dp[i] = max(dp[i-A[j]]+B[j]-A[j],dp[i])
        return dp[n]

    count1 = change(N,A,B,first_use)
    count2 = change(count1,B,A,second_use)

    print(count2)

solve()
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():

	s = tuple(input())
	length = len(s)

	dp = [[0 for _ in range(13)]for _ in range(length+1)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[1][i] = 1
	else:
		dp[1][int(s[-1])] = 1

	for i in range(1,length):
		if s[-i-1] != '?':
			num = (int(s[-i-1]) * (10**i)) % 13
			for j in range(13):
				dp[i+1][j] = dp[i][(13-num+j)%13]
				dp[i+1][j] %= MOD
		else:
			num = (10**i) % 13
			a = 0
			for j in range(10):
				for k in range(13):
					dp[i+1][k] += dp[i][(13-a+k)%13]
					dp[i+1][k] %= MOD
				a += num

	print(dp[length][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

N, M = map(int, input().split())
O =  [0]*N
B = [[0 for i in range(N)] for j in range (N)]
a = list(map(int, input().split()))
for i in range(N):
  O[i] = a[i]
 
for j in range(M):
  o_1, o_2 = map(int, input().split())
  B[o_1-1][o_2-1] = 1
  B[o_2-1][o_1-1] = 1
 
ans = 0
for k in range(N):
  flag =1
  for l in range(N):
    if B[k][l] == 1 and O[k] <= O[l]:
      flag = 0
  if  flag ==1:
    ans += 1
print(ans)
      

### FIXED CODE ###

N, M = map(int, input().split())
O = list(map(int, input().split()))
B = [[] for i in range(N)]
 
for j in range(M):
  o_1, o_2 = map(int, input().split())
  B[o_1-1].append(o_2-1)
  B[o_2-1].append(o_1-1)

ans = 0
for node in range(N):
  flag =1
  for l in B[node]:
    if O[node] <= O[l]:
      flag = 0
  if  flag ==1:
    ans += 1
print(ans)
### BUGGY CODE ###

S = input()

num_mod = 10 ** 9 + 7
dp = [1] + [0]*12
for i in range(len(S)):
  nextdp = [0] * 13
  if S[i] == '?':
    for j in range(13):
      for k in range(10):
        nextdp[(j*10 + k)%13] += dp[j]
  else:
    for j in range(13):
      nextdp[(j*10 + int(S[i]))%13] += dp[j]
  for j in range(13):
    nextdp[j] %= num_mod
  dp = nextdp
  # print(dp)
print(dp[5])

### FIXED CODE ###

S = input()
# S = '?'*100000

num_mod = 10 ** 9 + 7
dp = [1] + [0]*12

for i in range(len(S)):
  nextdp = [0] * 13
  if S[i] == '?':
    for j in range(13):
      for k in range(10):
        nextdp[(j*10 + k)%13] += dp[j]
  else:
    for j in range(13):
      nextdp[(j*10 + int(S[i]))%13] += dp[j]
  for j in range(13):
    nextdp[j] %= num_mod
  dp = nextdp
  # print(dp)
print(dp[5])
### BUGGY CODE ###

def main():
    N = int(input())
    # [4, 3, 3, 1, 3, 2]
    A = [int(input()) for _ in range(N)]
    current_max = max(A[1:N])
    # print('---')
    print(current_max)
    previous_max = current_max
    for i in range(1, N):
        A_tmp = A[0:i] + A[i+1:N]
        if previous_max in A_tmp:
            current_max = max([A[i-1], previous_max])
        else:
            current_max = max(A[0:i] + A[i+1:N])
        print(current_max)
        previous_max = current_max


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    # [4, 3, 3, 1, 3, 2]
    A = [int(input()) for _ in range(N)]
    current_max = max(A[1:N])
    current_max_index = A.index(current_max)
    # print('---')
    print(current_max)
    previous_max = current_max
    previous_max_index = current_max_index
    for i in range(1, N):
        # A_tmp = A[0:i] + A[i+1:N]
        if i != previous_max_index:
            current_max = max([A[i-1], previous_max])
            current_max_index = previous_max_index
        else:
            current_max = max(A[0:i] + A[i+1:N])
            current_max_index = A.index(current_max)
        print(current_max)
        previous_max = current_max
        previous_max_index = current_max_index


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

from collections import deque

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

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

gcd_max=1

import functools

prefix_gcd = 0
post = A
for i in range(N):
    a = post.popleft()
    if len(post) == 0:
        postfix_gcd = 0
    elif len(post) == 1:
        postfix_gcd = post[0]
    else:
        postfix_gcd = functools.reduce(gcd, post)
    if postfix_gcd == 0:
        gcd_max = max(gcd_max, prefix_gcd)
    if prefix_gcd > 0:
        gcd_max = max(gcd_max, gcd(prefix_gcd, postfix_gcd))
        prefix_gcd = gcd(prefix_gcd, a)
    else:
        gcd_max = max(gcd_max, postfix_gcd)
        prefix_gcd = a

print(gcd_max)


### FIXED CODE ###

from collections import deque
from copy import copy
from array import array

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

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

def get_prefix_gcd_list(Adeque):
    prefix_gcd = array('i', [0]*N)
    # marker
    prefix_gcd[0] = 0
    # the first itself is gcd
    prefix_gcd[1] = Adeque.popleft()
    for i in range(2,N):
        a = Adeque.popleft()
        prefix_gcd[i] = gcd(prefix_gcd[i-1], a)
        pass
    return prefix_gcd
        
    
# PREFIX_GCD[i]...i より前の要素のGCD
PREFIX_GCD = get_prefix_gcd_list(deque(copy(A)))

# PREFIX_GCD[i]...i より後の要素のGCD
POSTFIX_GCD=list(reversed(get_prefix_gcd_list(deque(reversed(A)))))

gcd_max=1

for i in range(N):
    pre = PREFIX_GCD[i]
    pos = POSTFIX_GCD[i]
    if pre == 0:
        _gcd = pos
    elif pos == 0:
        _gcd = pre
    else:
        _gcd = gcd(pre,pos)
    gcd_max = max(gcd_max, _gcd)
        
print(gcd_max)
### BUGGY CODE ###

def main():
    # 入力
    n = int(input())

    min_l = 10

    for i in range(1, n+1):
        if n % i != 0:
            continue
        j = int(n / i)

        il = len(str(i))
        jl = len(str(j))
        f = max(il, jl)
        if f < min_l:
            min_l = f
        if il == jl or il > jl:
            break

    print(min_l)


main()


### FIXED CODE ###

def main():
    # 入力
    s = input()

    x = len(s)
    limit = int(x/2)+1 if x % 2 == 0 else int(x/2)+2
    limit2 = int(x/2) if x % 2 == 0 else int(x/2)+1

    n = int(s)

    min_l = 11

    # ccc = 0
    for i in range(1, n+1):
        # ccc += 1
        il = len(str(i))
        if il == limit:
            break
        if n % i != 0:
            continue
        if il == min_l:
            break
        j = int(n / i)

        jl = len(str(j))
        f = max(il, jl)
        if f < min_l:
            min_l = f
        if jl == limit2 or il == jl or il > jl:
            break


    # print(ccc)
    print(min_l)


main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)


def dp_func(i):

    #if dp[i] < float('inf'):return dp[i]

    if i==0 :return 0
    #print(i)
    if dp[i] < float('inf'):return dp[i]

    for _ in range(1,K+1):
        if i==1:
            #a[i].append(abs(h[i]-h[i-1]))
            dp[i] = abs(h[i]-h[i-1])
            break

        if((i-_) >= 0):
            #print(i,_,i-_,h[i],h[i-_])
            b = (dp_func(i-_) + abs(h[i]-h[i-_]))
            dp[i] = min(dp[i],b)
            #a[i].append((dp_func(i-_) + abs(h[i]-h[i-_])))


    #print(i,a[i])
    #dp[i] = min(a[i])
    return dp[i]



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

dp = [float('inf')]*N
dp[0] = 0
a = [[] for _ in range(N)]

print(dp_func(N-1))
#print(dp)


### FIXED CODE ###

import sys
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
h = np.array(h)

dp = np.zeros(n, dtype=int)

#print(dp)
#print(h)

for i in range(1,n):
    start = max(0,i-k)
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

n = int(input())

a = list(int(i) for i in input().split())
b = []
for i in range(0,len(a)):
    b.append(a[i])


def solve(cnt,A,N):
    for i in range(1, N):
        if sum(A[0:i])>0:
            if sum(A[0:i+1])>=0:
                r = A[i]
                A[i]=-sum(A[0:i])-1
                cnt+=abs(r-A[i])
        else:
            if sum(A[0:i+1])<=0:
                r = A[i]
                A[i]=-sum(A[0:i])+1
                cnt+=abs(r-A[i])
    return cnt

cnt1=0
if b[0]<=0:
    ini=b[0]
    b[0]=1
    cnt1=abs(1-ini)


ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    ini=a[0]
    a[0]=-1
    cnt2=abs(-1-ini)


ans2=solve(cnt2,a,n)
print(min(ans1,ans2))


### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
b = [i for i in a]


def solve(cnt,A,N):
    sumA=A[0]
    for i in range(1, N):
        if sumA>0:
            if sumA+A[i]>=0:
                r = A[i]
                A[i]=-sumA-1
                cnt+=abs(r-A[i])
        else:
            if sumA+A[i]<=0:
                r = A[i]
                A[i]=-sumA+1
                cnt+=abs(r-A[i])

        sumA+=A[i]
    return cnt

cnt1=0
if b[0]<=0:
    ini=b[0]
    b[0]=1
    cnt1=abs(1-ini)


ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    ini=a[0]
    a[0]=-1
    cnt2=abs(-1-ini)


ans2=solve(cnt2,a,n)

print(min(ans1,ans2))
### BUGGY CODE ###

# AGC033A - Darker and Darker
# https://docs.scipy.org/doc/scipy/reference/generated/scipy.ndimage.distance_transform_bf.html
from scipy.ndimage import distance_transform_bf as dist


def main():
    """
    distance_transform_bf:
        orig     taxicab / chessboard / euclidean
        1 1 1     2 1 2      1 1 1      1.4 1 1.4
        1 0 1 ->  1 0 1      1 0 1       1  0  1
        1 1 1     2 1 2      1 1 1      1.4 1 1.4
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = tuple(tuple(input()) for _ in range(h))
    B = tuple(tuple(1 if i == "." else 0 for i in a) for a in A)
    D = dist(B, metric="taxicab")
    print(D.max())


if __name__ == "__main__":
    main()

### FIXED CODE ###

# AGC033A - Darker and Darker
from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        0 0 0    1 1 1
        0 1 0 -> 1 0 1
        0 0 0    1 1 1
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = list(list(input()) for _ in range(h))
    B = [[1 if i == "." else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    print(D.max())


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

N=int(input())
A=[int(input()) for i in range(N)]
S=list(set(A))
C=[0]*len(S)

for i in range(N):
    C[S.index(A[i])]+=1

ans=0
for i in C:
    if i%2==1:
        ans+=1

print(ans)

### FIXED CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
c=1
ans=0

for i in range(1,N):
    if A[i]!=A[i-1]:
        if c%2==1:
            ans+=1
        c=1
    else:
        c+=1

if c%2==1:
    ans+=1

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

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
A_sum=sum(A)
A_count=[]
for i in range(100001):
    A_count.append(A.count(i))
for i in range(Q):
    A_sum+=(BC[i][1]-BC[i][0])*A_count[BC[i][0]]
    A_count[BC[i][1]]+=A_count[BC[i][0]]
    print(A_sum)

### FIXED CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
#BC=[]
#for i in range(Q):
#    BC.append(list(map(int,input().split())))
A_sum=sum(A)
A_count=Counter(A)

for i in range(Q):
    B,C=(map(int,input().split()))
    A_sum+=(C-B)*A_count[B]
    A_count[C]+=A_count[B]
    A_count[B]=0
    print(A_sum)
### BUGGY CODE ###

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

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
mod = (10**9) + 7
t = 0
sum = 0
for i in range(1,n):
    sum += A[i]
for i in range(n-1):
    t += (A[i]*sum)%mod
    sum -=  A[i+1]
t = t%mod
print(t)
### BUGGY CODE ###

from itertools import combinations
s = input()
tmp = []
num = ["0"]
for char in s:
    tmp.append(char)
    num.append("".join(tmp))

c = 0
for m, n in combinations(num, 2):
    if m == "0":
        check = int(n)
    else:
        check = int(n) - int(m) * 10 ** (len(n) - len(m))
    if check % 2019 == 0:
        c += 1

print(c)


### FIXED CODE ###

from itertools import combinations
s = input()
d = {0: 1}
tmp = 0
i = 0
for char in s[::-1]:
    tmp += int(char) * pow(10, i, 2019)
    tmp %= 2019
    if tmp not in d:
        d[tmp] = 1
    else:
        d[tmp] += 1
    i += 1

result = 0
for num, v in d.items():
    result += v * (v - 1) // 2

print(result)