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

'''
.append(要素) リストに要素を追加 
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
from functools import reduce
from operator import mul

f = [int(s) for s in stdin.readline().rstrip().split()]
N = f[0]
K = f[1]
p = [int(s) for s in stdin.readline().rstrip().split()]
past = -2000
resNum = -2000
for el in range(N - K + 1):
    data = copy.copy(p)
    tar = sum(data[el: el + K])
    if past < tar:
        past = tar
        resNum = el
res = p[resNum: resNum + K]
result = 0
for el in res:
    result += (1/2+el/2)
print(result)


### FIXED CODE ###

'''
.append(要素) リストに要素を追加 
.extend(リスト) リストを連結する
.insert(場所,要素) 指定した場所に要素追加
del 配列名[場所]
-1で末尾で末尾から一つ前

sort()
sorted(reverse=true)

配列の初期化
配列名=[a]*n+[b]*m

Decimal()
'''

from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
from functools import reduce
from operator import mul

f = [int(s) for s in stdin.readline().rstrip().split()]
N = f[0]
K = f[1]
p = list(map(lambda x: 1/2+x/2, [int(s)
                                 for s in stdin.readline().rstrip().split()]))
E = []
tmp = 0
for el in p:
    tmp += el
    E.append(tmp)
past = E[K - 1]
for el in range(len(E)):
    if el - K < 0:
        continue
    e = E[el] - E[el - K]
    if past < e:
        past = e
print(past)
### BUGGY CODE ###

n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)

import numpy as np
ans=0
now=np.array([], dtype="int64")
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        now=np.append(now,b)
    #print(nouki, now)
    if now.size==0:continue
    m=np.max(now)
    ans+= m
    now= np.delete(now,np.argmax(now))

print(ans)
    


### FIXED CODE ###

n,m=map(int,input().split())
A=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append([a,b])
A=sorted(A, key=lambda x:(x[0], -x[1]))
from collections import deque
A=deque(A)

# import numpy as np
import bisect as bi
ans=0
now=[]
for nouki in range(1,m+1):
    while A:
        a,b=A.popleft()
        if a>nouki: A.appendleft([a,b]);break
        bi.insort(now,b)
    #print(nouki, now)
    if now==[]:continue
    ans+= now[-1]
    del now[-1]


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

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(m)]
rule = [[] for _ in range(n)]
for i in range(m):
    rule[data[i][0] - 1].append(data[i][1])
    rule[data[i][1] - 1].append(data[i][0])
res = rule[0][:]
ans = 0
for j in range(n - 1):
    if j + 2 not in res:
        for k in range(len(rule[j + 1])):
            res.append(rule[j + 1][k])
    else:
        ans += 1
        res = []
        for k in range(len(rule[j + 1])):
            res.append(rule[j + 1][k])
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n, m = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = rule[j + 1][:]
    print(ans)


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

from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    for i in range(2,n//1 + 1):
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
    if cnt == 0 and tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)

### FIXED CODE ###

from fractions import gcd
def f(n):
    tmp = n
    cnt = 0
    i = 2
    while i <= n**0.5 + 1:
        if tmp < i:
            break
        if tmp % i == 0:
            cnt += 1
            while tmp % i == 0:
                tmp //= i
        i += 1
    if tmp != 1:
        cnt += 1
    return cnt

A, B = map(int, input().split())
g = gcd(A, B)
ans = f(g) + 1
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
max_l = [0]*K
for i in range(N):
  tmp_l = p[i:i+K]
  if sum(tmp_l) > sum(max_l):
    max_l = tmp_l
print(sum([(n+1)/2 for n in max_l]))

                          

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
max_l = 0
point = sum(p[:K])
index = 0

for i in range(1,N-K+1):
  point -= (p[i-1] - p[i+K-1])
  if point > max_l:
    max_l = point
    index = i
print(sum([(n+1)/2 for n in p[index:index+K]]))
### BUGGY CODE ###

import numpy as np
N = int(input())
alist = np.array(list(map(int, input().split())))
alist
alistp = alist + 1
alistm = alist - 1
alists = np.hstack([alistm, alist, alistp])
k = []
d = {}
for a in alists:
    if a not in k:
        k.append(a)
        d[a] = 1
    else:
        d[a] += 1
print(max(d.values()))

### FIXED CODE ###

import numpy as np
N = int(input())
alist = np.array(list(map(int, input().split())))
alist
alistp = alist + 1
alistm = alist - 1
d = {}
for a in alist:
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1
for a in alistp:
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1
for a in alistm:
    if a not in d.keys():
        d[a] = 1
    else:
        d[a] += 1
print(max(d.values()))
### BUGGY CODE ###

from itertools import *
n=range(49994);a=list(n)
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in iter(input,'0'):
 x=int(x)
 if x%2:print(sum(1 for c in p[1:x]if 2+c==x))
 elif x-4:print(sum(1 for a in p[1:x]for b in p[1:x]if a+b==x))
 else:print(1)


### FIXED CODE ###

import bisect,sys
from itertools import *
n=range(50001);a=list(n);a[1]=0
for i in range(2,224):a[i*2::i]=[0]*len(a[i*2::i])
p=list(compress(n,a))
for x in map(int,sys.stdin):
 if x:print(len([1 for d in p[:bisect.bisect(p,x//2)]if a[x-d]]))
### BUGGY CODE ###

K=int(input())
if K%2==0 or K%5==0:
	print("-1")
	exit()
for n in range(1,10**6+1):
	if (7*(10**n-1)//9)%K==0:
		print(n)
		exit()
print("-1")

### FIXED CODE ###

K=int(input())
base=7%K
for i in range(1,K+1):
	if base%K==0:
		print(i)
		exit()
	else:
		base=(base*10+7)%K
print(-1)
### BUGGY CODE ###

n,k=map(int,input().split())
arr=list(map(int,input().split()))
pos=[[] for _ in range(2*10**5+1)]
pos[0].append(-1)
arrpos=[0]*n
for i in range(n):
  pos[arr[i]].append(i)
  arrpos[i]=len(pos[arr[i]])
ans=[]
tmp=[0]
cnt=0
while len(tmp)!=0:
  p=pos[tmp[0]][0]+1
  ntmp=[]
  flag=True
  while p<n:
    if arrpos[p]<len(pos[arr[p]]):
      p=pos[arr[p]][arrpos[p]]+1
    else:
      ntmp.append(arr[p])
      if len(pos[arr[p]])!=1:
        flag=False
      p+=1
  ans.append(ntmp)
  tmp=ntmp
  cnt+=1
  if flag==True:
    break
for i in range(1,len(tmp)+1):
  ans.append(tmp[i:])
print(*ans[k%len(ans)-1])

### FIXED CODE ###

import collections

n,k=map(int,input().split())
arr=list(map(int,input().split()))
pos=[[] for _ in range(max(arr)+1)]
for i in range(2*n):
  pos[arr[i%n]].append(i)
edge=[[] for _ in range(n)]
cnt=collections.defaultdict(int)
for i in range(n):
  s=pos[arr[i]][cnt[arr[i]]]
  g=pos[arr[i]][cnt[arr[i]]+1]
  edge[s].append((g+1)%n)
  edge[s].append((g+1)//n)
  cnt[arr[i]]+=1
start=0
loop=0
for _ in range(n):
  loop+=edge[start][1]
  start=edge[start][0]
  if start==0:
    break
k%=loop
if k==0:
  print('')
else:
  k-=1
  start=0
  loop=0
  for _ in range(n):
    if loop==k:
      break
    loop+=edge[start][1]
    start=edge[start][0]
  s=set()
  q=collections.deque()
  for i in range(start,n):
    if arr[i] not in s:
      s.add(arr[i])
      q.append(arr[i])
    else:
      while 1:
        tmp=q.pop()
        s.discard(tmp)
        if tmp==arr[i]:
          break
  print(*list(q))
### BUGGY CODE ###

from collections import deque


line = input().split(" ")
N, K = int(line[0]), int(line[1])
line = input().split(" ")
dices = [int(c) for c in line]

max_E = 0
expectations = deque([0] * K, maxlen=K)

E = 0
for dice in dices:
    E -= expectations.popleft()
    e = sum(range(1, dice + 1)) / dice
    expectations.append(e)
    E += e
    if E < max_E:
        continue
    else:
        max_E = E

print(max_E)


### FIXED CODE ###

from collections import deque


line = input().split(" ")
N, K = int(line[0]), int(line[1])
line = input().split(" ")
dices = [int(c) for c in line]

max_E = 0
expectations = deque([0] * K, maxlen=K)
e_memo = {}
E = 0
for dice in dices:
    E -= expectations.popleft()
    if e_memo.get(dice) is None:
        e_memo[dice] = sum(range(1, dice + 1)) / dice
    e = e_memo[dice]
    expectations.append(e)
    E += e
    if E < max_E:
        continue
    else:
        max_E = E

print(max_E)
### BUGGY CODE ###

N, M = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
BC = []
for m in range(M):
  b,c = map(int,input().split())
  BC.append([b,c])
BC = sorted(BC, key=lambda x: x[1], reverse=True)
L = []
for i in range(M):
  for j in range(BC[i][0]):
    L.append(BC[i][1])
for i in range(min(N,len(L))):
  if A[i] < L[i]:
    A[i] = L[i]
  else:
    break
print(sum(A))



### FIXED CODE ###

import heapq
from heapq import heapify

N, M = map(int,input().split())
A = list(map(int,input().split()))
L = []
for i in range(N):
  L.append([A[i],1])
for i in range(M):
  b, c = map(int,input().split())
  L.append([c,b])
heapq._heapify_max(L)

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappop_max(heap):
    lastelt = heap.pop()
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        heapq._siftup_max(heap, 0)
        return returnitem
    return lastelt

ans = 0
for i in range(N):
  x = _heappop_max(L)
  if x[1] > 1:
    ans += x[0]
    x[1] -= 1
    _heappush_max(L,x)
  else:
    ans += x[0]
print(ans)
### BUGGY CODE ###

from collections import deque
from copy import copy, deepcopy
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)


ans = [0]*N
visited = [False]*N
visited[0]=True
ans[0] = 1
d = deque([(0,[A[0]])])
while len(d)>0:
    v,LIS = d.popleft()
    for u in edge[v]:
        if visited[u]==False:
            visited[u] = True
            lis = copy(LIS)
            ind = bisect_left(lis,A[u])
            if ind < len(lis):
                lis[ind] = A[u]
            else:
                lis.append(A[u])
            ans[u] = len(lis)
            d.append((u,lis))
print(*ans, sep='\n')

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            if A[u] > LIS[-1]:
                LIS.append(A[u])
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS.pop()
            else:
                ind = bisect_left(LIS,A[u])
                stack = LIS[ind]
                LIS[ind] = A[u]
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS[ind] = stack
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split(" ")))

L.sort()

num_triangles = 0
for i in range(N): # stick 1
    for j in range(i+1, N): # stick 2; must be larger than 1
        # if a<b then we require c<b+a
        idx = bisect_left(a=L, x=L[i]+L[j]) # find the index at which c<b+a
        num_triangles += max(0, idx-(j+1)) # c can be, at minimum, b=c
print(num_triangles)


### FIXED CODE ###

from bisect import bisect_left

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

ans = 0
for i in range(n):
    for j in range(i+1, n):
        endpt = bisect_left(l, l[i] + l[j])
        ans += endpt-j-1

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

n = int(input())
A = list(map(int, input().split()))
ans = 0
for j in range(61):
  c = 0
  for i in A:
    if i>>j & 1:
      c += 1
  ans += 2**j*((n-c)*c)
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for j in range(61):
  c = 0
  for i in A:
    if i>>j & 1:
      c += 1
  ans += 2**j*((n-c)*c)
print(ans%(10**9+7))
### BUGGY CODE ###

from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print(max(dp.values()))

### FIXED CODE ###

from collections import defaultdict
N, W = [int(i) for i in input().split()]
Things = [[int(i) for i in input().split()] for j in range(N)]

dp = defaultdict(int)
dp[0] = 0
for w, v in Things:
    for nw, nv in list(dp.items()):
        if nw + w <= W:
            dp[nw + w] = max(dp[nw + w], nv + v)
print(max(dp.values()))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
memo = {}
def search(x):
    if x in memo:
        return memo[x]

    sx = str(x)
    sn = len(sx)

    if sn == 1:
        if x <= 5:
            return x
        else:
            return 11 - x

    if int(sx[0]) < 9:
        p = int(sx[0]) + 1
    else:
        p = 1
    res1 = search(int(sx[1:])) + int(sx[0])
    res2 = search((int(sx[0]) + 1) * (10 ** (sn - 1)) - x) + p

    memo[x] =  min(res1, res2)
    return memo[x]

print(search(n))

### FIXED CODE ###

n = input()
x = len(n)
inf = 10 ** 9
#dp[i][flg]...i桁目まで、未満フラグ=1
dp = [[inf] * 2 for _ in range(x+1)]
dp[0][0] = 0
dp[0][1] = 1
for i in range(x):
    s = int(n[i])
    dp[i+1][0] = min(dp[i][0] + s, dp[i][1] + 10 - s)
    dp[i+1][1] = min(dp[i][0] + s + 1, dp[i][1] + 9 - s)

print(dp[x][0])
### BUGGY CODE ###

n = int(input())
z = []
pre = 0
for _ in range(n):
    i = int(input())
    if i != pre:
        z.append(i)
    pre = i
n = len(z)
dp = [1] * (n+1)
place = {}
for i in range(n):
    dp[i+1] = dp[i]
    if z[i] not in place:
        place[z[i]] = {i}
    else:
        for p in place[z[i]]:
            dp[i+1] += dp[p]
        place[z[i]].add(i)
    dp[i+1] %= 10 ** 9 + 7
print(dp[n])

### FIXED CODE ###

n = int(input())
z = []
pre = 0
for _ in range(n):
    i = int(input())
    if i != pre:
        z.append(i)
    pre = i
n = len(z)
dp = [1] * (n+1)
dpp = [0] * 2 * 10 ** 5
for i in range(n):
    dp[i+1] = dp[i] + dpp[z[i]-1]
    dpp[z[i]-1] += dp[i]
    dp[i+1] %= 10 ** 9 + 7
print(dp[n])
### BUGGY CODE ###

import bisect
import copy

n = int(input())
list1 = list(map(int,input().split()))
list1.sort()

cout = 0
m,k = 0,0

for i in range(n-2):
	o = list1.pop(0)
	list1_c = copy.deepcopy(list1) #ここでjのためのdeepcopyを更新
	for j in range(n-i-1):
		p = list1_c.pop(0)

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		d = bisect.bisect_right(list1_c,b)
		
		cout += d

print(cout)

### FIXED CODE ###

import bisect
import copy

n = int(input())
list1 = list(map(int,input().split()))
list1.sort()

cout = 0
m,k = 0,0

for i in range(n-2):
	o = list1.pop(0)
	for j in range(n-i-1):
		p = list1[j]

		a = abs(o-p) +1
		b = o+p -1 #<= ではなく<条件に揃える

		d = bisect.bisect_right(list1[j+1:],b)
		
		cout += d

print(cout)
### BUGGY CODE ###

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

mod = 10**9 + 7
num_sum = 0

for i in range(N-1):
  for j in range(i+1, N):
    num_sum += num_list[i] * num_list[j]

print(num_sum % mod)



### FIXED CODE ###

N = int(input())
num_list = list(map(int, input().split()))
mod = 10**9 + 7

sum_num = 0
sum_list = []
for num in num_list:
  sum_num += num
  sum_num = sum_num % mod
  sum_list.append(sum_num)

answer = 0
for i in range(N):
  sum_num -= num_list[i]
  sum_num = sum_num if sum_num >= 0 else sum_num + mod
  answer += num_list [i] * sum_num
  answer = answer % mod

print(answer)
### BUGGY CODE ###

# 操作回数を入力する
N = int(input())
# 言う数字を入力する
list_A = [int(input()) for _ in range(N)]
# 終了後に残っている数字の数を設定する
ans = 0
# 数字の種類のリストを作成する
num_list = list(set(list_A))
# それぞれの数字について、、
for num in num_list:
    # 言われる回数を求める
    count = list_A.count(num)
    # 奇数回言われる場合、ansを増やす
    if count % 2 != 0:
        ans += 1
# 結果を出力する
print(ans)

### FIXED CODE ###

import bisect
# 操作回数を入力する
N = int(input())
# 言う数字を入力する
list_A = [int(input()) for _ in range(N)]
# 紙の状態を設定する
paper = []
# 
for A in list_A:
    if paper == []:
        paper.append(A)
        continue
    # 紙上のAをニ分探索する
    index = bisect.bisect_left(paper, A)
    if index < len(paper) and paper[index] == A:
        del paper[index]
    else:
        paper.insert(index, A)
# 結果を出力する
print(len(paper))
### BUGGY CODE ###

#input
N = int(input())
S = [sorted(input()) for i in range(N)]

ana = 0
for i in range(N):
    ana += S.count(S[i])

print(int((ana - N) / 2))

### FIXED CODE ###

import collections

#input
N = int(input())
S = [''.join(sorted(input())) for i in range(N)]

S = collections.Counter(S)

ans = 0
for k, v in S.items():
    ans += v * (v-1) // 2

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

import sys
from heapq import heappop as p
sys.setrecursionlimit(9**9)
n=int(input())
T=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a-1].append([b-1,i])
C=[0]*(n-1)
def f(Q):
    R=[]
    for q in Q:
        H=list(range(1,n))
        for t in T[q[0]]:
            x=p(H)
            if x==q[1]:
                x=p(H)
            C[t[1]]=x
            if len(T[t[0]])!=0:
            	R.append([t[0],x])
    if len(R)!=0:
    	return f(R)
f([[0,0]])
print(max(C))
for c in C:
    print(c)

### FIXED CODE ###

import sys
sys.setrecursionlimit(9**9)
n=int(input())
T=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    T[a-1].append([b-1,i])
C=[0]*(n-1)
def f(i,r):
    c=1
    for (x,y) in T[i]:
        c+=(c==r)
        C[y]=c
        f(x,c)
        c+=1
f(0,0)
print(max(C))
for c in C:
    print(c)
### BUGGY CODE ###

A, B, N = map(int, input().split())
result = 0
for i in range(N+1):
    a = (A * i) // B - A * (i // B)
    if a > result:
        result = a
print(result)

### FIXED CODE ###

A, B, N = map(int, input().split())
#result = int(((N/B-int(N/B))*A))
ma = min(N,B-1)
result = int(((ma/B-int(ma/B))*A))
print(result)
### BUGGY CODE ###

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

mod = pow(10,9)+7

K = 60
P = [0]*K
Z = [0]*K
for a in A:
    n = a
    for i in range(K):
        b = n%2
        if b:P[i]+=1
        else:Z[i]+=1
        n//=2
ans = 0
for k in range(K):
    ans+=(pow(2,k,mod)*(P[k]*Z[k]))%mod
print(ans%mod)

### FIXED CODE ###

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

mod = pow(10,9)+7

K = 60
P = [0]*K
Z = [0]*K
for a in A:
    n = a
    for i in range(K):
        b = n%2
        if b:P[i]+=1
        else:Z[i]+=1
        n//=2
ans = 0
for k in range(K):
    ans+=(pow(2,k,mod)*(P[k]*Z[k]))%mod
print(ans%mod)
### BUGGY CODE ###



n = input()
p = map(float, raw_input().split())

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    pi = p[i - 1]
    for j in range(i + 1):
        dp[i][j] = pi * dp[i - 1][j - 1] + (1 - pi) * dp[i - 1][j]
resp = 0
for i in range(n / 2 + 1, n + 1):
    resp += dp[n][i]
print(resp)


### FIXED CODE ###


n = input()
p = map(float, raw_input().split())

dp = [[0] * (n + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    pi = p[i - 1]
    for j in range(i + 1):
        dp[i][j] = pi * dp[i - 1][j - 1] + (1 - pi) * dp[i - 1][j]
resp = 0
for i in range(n / 2 + 1, n + 1):
    resp += dp[n][i]
print(resp)
### BUGGY CODE ###

from collections import deque
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
mod = 10**9+7
fact = [1]*(N+1)
fact_inv = [1]*(N+1)
for i in range(1,N+1):
  fact[i] = (fact[i-1]*i)%mod
  fact_inv[i] = pow(fact[i], mod-2, mod)

g = [deque([]) for _ in range(N+1)]
for a,b in ab:
  g[a].append(b)
  g[b].append(a)
  
parents = [0]*(N+1)
q = deque([])
s = deque([1])
while s:
  x = s.pop()
  q.append(x)
  for y in g[x]:
    if y==parents[x]:
      continue
    else:
      parents[y] = x
      s.append(y)
      
q = list(q)
size_forward = [0]*(N+1)
dp_forward = [1]*(N+1)
for i in q[::-1]:
  p = parents[i]
  s = size_forward[i] + 1
  size_forward[p] += s
  dp_forward[i] *= fact[size_forward[i]]
  dp_forward[p] *= dp_forward[i] * fact_inv[s]
  dp_forward[p] %= mod
  
size_back = [N-1-i for i in size_forward]
dp_back = [1]*(N+1)
for i in q[1:]:
  p = parents[i]
  x = dp_back[p]
  x *= fact_inv[size_back[p]]
  x *= dp_forward[p]
  x *= fact_inv[size_forward[p]]
  x *= fact[size_forward[i]+1]
  x *= pow(dp_forward[i],mod-2,mod)
  x *= fact[size_back[i]-1]
  dp_back[i] = x % mod
  
for a,b,c,d in zip(size_forward[1:], dp_forward[1:], size_back[1:], dp_back[1:]):
  ans = b * d * fact[a+c] * fact_inv[a] * fact_inv[c]
  ans %= mod
  print(ans)

### FIXED CODE ###

from collections import deque
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
mod = 10**9+7
fact = [1]*(N+1)
fact_inv = [1]*(N+1)
for i in range(1,N+1):
  fact[i] = (fact[i-1]*i)%mod
  
fact_inv[-1] = pow(fact[-1], mod-2, mod)
for i in range(N,0,-1):
  fact_inv[i-1] = fact_inv[i] * i % mod

g = [deque([]) for _ in range(N+1)]
for a,b in ab:
  g[a].append(b)
  g[b].append(a)
  
parents = [0]*(N+1)
q = deque([])
s = deque([1])
while s:
  x = s.pop()
  q.append(x)
  for y in g[x]:
    if y==parents[x]:
      continue
    else:
      parents[y] = x
      s.append(y)
      
q = list(q)
size_forward = [0]*(N+1)
dp_forward = [1]*(N+1)
for i in q[::-1]:
  p = parents[i]
  s = size_forward[i] + 1
  size_forward[p] += s
  dp_forward[i] *= fact[size_forward[i]]
  dp_forward[p] *= dp_forward[i] * fact_inv[s]
  dp_forward[p] %= mod
  
size_back = [N-1-i for i in size_forward]
dp_back = [1]*(N+1)
for i in q[1:]:
  p = parents[i]
  x = dp_back[p]
  x *= fact_inv[size_back[p]]
  x *= dp_forward[p]
  x *= fact_inv[size_forward[p]]
  x *= fact[size_forward[i]+1]
  x *= pow(dp_forward[i],mod-2,mod)
  x *= fact[size_back[i]-1]
  dp_back[i] = x % mod
  
for a,b,c,d in zip(size_forward[1:], dp_forward[1:], size_back[1:], dp_back[1:]):
  ans = b * d * fact[a+c] * fact_inv[a] * fact_inv[c]
  ans %= mod
  print(ans)
### BUGGY CODE ###

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

for x in A:
  for i in range(60):
    B[i] += (x >> i) & 1

ans = 0
p = 1

for i in range(60):
  if i >= 1:
    p *= 2
    p %= mod
  ans += (N-B[i])*B[i]*p
  ans %= mod

print(ans)

### FIXED CODE ###

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

for x in A:
  for i in range(60):
    B[i] += (x >> i) & 1

ans = 0
p = 1

for i in range(60):
  if i >= 1:
    p *= 2
    p %= mod
  ans += (N-B[i])*B[i]*p
  ans %= mod

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

n=int(input())
a=[int(input()) for i in range(n)]
x=[]
for ai in a:
  if ai in x:
    x.pop(x.index(ai))
  else:
    x.append(ai)
print(len(x))

### FIXED CODE ###

from collections import Counter
n = int(input())
a = [int(input()) for i in range(n)]
ans = 0
c = Counter(a)
for i in c.values():
    if i%2!=0:
        ans+=1
print(ans)