Harryxun/stf_run huggingface dataset:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(300000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur])
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [99999999] * (n+1)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)

### FIXED CODE ###

import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(230000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur], 0, lis+1)
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [999999999999] * (n+2)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)
N = int(input())
flag = 0

for cake in range(26):
    for donut in range(15):
        if cake*4 + donut*7 == N:
            flag = 1
            break
    if flag == 1:
        break

if flag = 1:
    print("Yes")
else :
    print("No")


### FIXED CODE ###

N = int(input())
flag = 0

for cake in range(26):
    for donut in range(15):
        if cake*4 + donut*7 == N:
            flag = 1
            break
    if flag == 1:
        break

if flag == 1:
    print("Yes")
else :
    print("No")
N = int(input())
SP = []
for _ in range(N):
    SP.append([i for i in input().split()])
for n in range(N):
    SP[n][1] = str(100 - int(SP[n][1])).rjust(3,'0')
SP2 = []
for n in range(N):
    SP2.append(SP[0]+SP[1])
ans = sorted(range(len(SP2)), key=lambda k: SP2[k])
[print(i) for i in ans]

### FIXED CODE ###

N = int(input())
SP = []
for _ in range(N):
    SP.append([i for i in input().split()])
for n in range(N):
    SP[n][1] = str(100 - int(SP[n][1])).rjust(3,'0')
SP2 = []
for n in range(N):
    SP2.append(SP[n][0]+SP[n][1])
ans = sorted(range(len(SP2)), key=lambda k: SP2[k])
for i in ans:
    print(i+1)
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
c=[]
for m in range(n):
  i=n-m
  x=n%i
  b[i-1]=a[i-1]
  for j in range(2,x+1):
    b[i-1]+=b[j*i-1]
  b[i-1]%=2
  if b[i-1]==1:
    c.append(i-1)

print(len(c))
for i in range(len(c)):
  print(c[i]+1,end=' ')

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[0]*n
c=[]
for m in range(n):
  i=n-m
  x=n//i
  b[i-1]=a[i-1]
  for j in range(2,x+1):
    b[i-1]+=b[j*i-1]
  b[i-1]%=2
  if b[i-1]==1:
    c.append(i-1)

print(len(c))
for i in range(len(c)):
  print(c[i]+1,end=' ')
a , b = map(int,input().spilit())

x = ( a * b )

if x % 2 == 0:
    print("Even")
else:
    print("odd")



### FIXED CODE ###

a, b = map(int, input().split())
answer = a * b
if answer % 2 == 0:
    print('Even')
else:
    print('Odd')
import numpy as np
mod=10**9+7
N=int(input())
A=np.array(list(map(int, input().split())))
ans=0
for　i in range(60):
  b=np.count_nonzero(A>>i&1)
  ans+=(2**i)*b*(N-b)
  ans%=mod
  
print(ans)



### FIXED CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int, input().split())))


mod = 10**9+7
ans = 0
#bitの60桁を見ていく
#桁ごとに分割して足していく
for i in range(60):
  #i桁目が1である要素数　N-b1はi桁目が0である要素数
  b1 = np.count_nonzero(A>>i&1)
  #bi * (N-b1) がxorを意味している
  ans += 2**i*b1*(N-b1)
  ans %= mod
print (ans)
def strToList(str,offset=0):
    res = [];
    for el in str.split(" "):
        if el!='':
            res.append(int(el)+offset)
    return res


[N,M,K] = strToList(input())
A = strToList(input())
B = strToList(input())

current_time = 0
current_value = 0
iA = 0
iB = 0

while iA<N:
    if current_time+A[iA]<=K:
        current_time+=A[iA]
        current_value+=1
        iA+=1
    else:
        break

max_value = current_value

while iA>=0 and iB<M:
    if current_time+B[iB]<=K:
        current_time+=B[iB]
        iB+=1
        current_value+=1
        if current_value>max_value:
            max_value=current_value
    else:
        current_time-=A[iA]
        iA-=1
        current_value-=1

print(max_value)


### FIXED CODE ###

def strToList(str,offset=0):
    res = [];
    for el in str.split(" "):
        if el!='':
            res.append(int(el)+offset)
    return res


[N,M,K] = strToList(input())
A = strToList(input())
B = strToList(input())

current_time = 0
current_value = 0
iA = 0
iB = 0

while iA<N:
    if current_time+A[iA]<=K:
        current_time+=A[iA]
        current_value+=1
        iA+=1
    else:
        break

max_value = current_value
iA-=1

while iA>-2 and iB<M:
    if current_time+B[iB]<=K:
        current_time+=B[iB]
        iB+=1
        current_value+=1
        if current_value>max_value:
            max_value=current_value
    else:
        current_time-=A[iA]
        iA-=1
        current_value-=1

print(max_value)
n, a, b = map(int, input().split())
mod = 10**9+7

#print(x*pow(y,(mod-2),mod)%mod)

def conv(n, x, mod):
    X = 1
    for i in range(x):
        k = i+1
        X *= (n-k+1)*pow(k,(mod-2),mod)%mod
        X %= mod
    return X

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

#print(conv(n, a, mod))
#print(conv(n, b, mod))

ans = power_func(2, n, mod) - conv(n, a, mod) - conv(n, b, mod) - 1
ans %= mod
print(ans)n, a, b = map(int, input().split())
mod = 10**9+7

#print(x*pow(y,(mod-2),mod)%mod)

def conv(n, x, mod):
    X = 1
    for i in range(x):
        k = i+1
        X *= (n-k+1)*pow(k,(mod-2),mod)%mod
        X %= mod
    return X

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

#print(conv(n, a, mod))
#print(conv(n, b, mod))

ans = power_func(2, n, mod) - conv(n, a, mod) - conv(n, b, mod) - 1
ans %= mod
print(ans)

### FIXED CODE ###

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

#print(x*pow(y,(mod-2),mod)%mod)

def conv(n, x, mod):
    X = 1
    for i in range(x):
        k = i+1
        X *= (n-k+1)*pow(k,(mod-2),mod)%mod
        X %= mod
    return X

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

#print(conv(n, a, mod))
#print(conv(n, b, mod))

ans = power_func(2, n, mod) - conv(n, a, mod) - conv(n, b, mod) - 1
ans %= mod
print(ans)
from itertools import accumulate
from collections import Counter

p = int(input().split()[1])
a = map(int, input())
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  a = accumulate(x * pow(10, i, p) for i, x in enumerate(reversed(a), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)


### FIXED CODE ###

from itertools import accumulate
from collections import Counter

p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  a = accumulate(x * pow(10, i, p) for i, x in enumerate(reversed(a), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)
import sys
input()
e = [[0, 0, 0]] + [list(map(int, e.split())) for e in sys.stdin]
for (t0, a0, b0), (t1, a1, b1) in zip(e, e[1:]):
    d = (t1 - t0) - abs(a1 - a0) - abs(b1 - b0)
    if d < 0 or t % 2 == 1:
        print('No')
        exit()
print('Yes')

### FIXED CODE ###

can = True
e = [[0, 0, 0]] + [list(map(int, input().split())) for _ in range(int(input()))]
for a, b in zip(e[1:], e):
    dt = a[0] - b[0]
    dist = abs(a[1] - b[1]) + abs(a[2] - b[2])
    if dt < dist: can = False; break
    if dt % 2 != dist % 2: can = False; break
print(['No', 'Yes'][can])
r =[int(i) for i in input().split()]

s = r * r *3.14
l = 2 * r *3.14

print("{0:.5f},{1:.5f}".format(s,l))

### FIXED CODE ###

import math
r = float(input())
 
s = r * r *math.pi
l = r *2 *math.pi
 
print("{0:.5f} {1:.5f}".format(s,l))
import math

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

if N == 1:
    print(A[0])
else:
    res = math.gcd(A[0], A[1])
    for i in range(2, N):
        res = math.gcd(res, A[i])
    print(res)

### FIXED CODE ###

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

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

if N == 1:
    print(A[0])
else:
    res = gcd(A[0], A[1])
    for i in range(2, N):
        res = gcd(res, A[i])
    print(res)
def gcd(a, b):
    while a != b:
        if a < b:
            b = b - a
        else:
            a = a - b
    return a

def m(a):
    a.sort()
    b = []
    for i in range(len(a) // 2):
        b.append(gcd(a[i], a[i + 1]))
    return b

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

while len(a) > 1:
    a = m(a)

print(g)


### FIXED CODE ###

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

def m(a):
    a.sort()
    l = len(a)
    b = []
    for i in range(l // 2):
        b.append(gcd(a[i], a[l - i - 1]))
    if l % 2 == 1:
        b.append(a[l // 2])
    return list(set(b))

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

while len(a) > 1:
    a = m(a)

print(a[0])
s,t=map(int,input().split())
print(s+t)

### FIXED CODE ###

左,右=map(str,input().split())
print(右+左)
N=int(input())
A=list(map(int, input().split()))
B=[]
B.append(A[0])
for i in range(1,N):
    if A[i]!=B[-1]: B.append(A[i])
i=1
length=len(B)
while i<length-1:
    if B[i]>B[i-1] and B[i]<B[i+1] or B[i]<B[i-1] and B[i]>B[i+1]:
        B.pop(i)
        length-=1
    else:
        i+=1
yen=1000
kabu=0
for i in range(len(B)):
    if B[0]<B[1]:
        if i%2==0 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        elif i%2==1:
            yen=yen+kabu*B[i]
    else:
        if i%2==1 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        elif i%2==0:
            yen=yen+kabu*B[i]
print(yen)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
B=[]
B.append(A[0])
for i in range(1,N):
    if A[i]!=B[-1]: B.append(A[i])
i=1
length=len(B)
while i<length-1:
    if B[i]>B[i-1] and B[i]<B[i+1] or B[i]<B[i-1] and B[i]>B[i+1]:
        B.pop(i)
        length-=1
    else:
        i+=1
yen=1000
kabu=0
for i in range(len(B)):
    if len(B)>=2 and B[0]<B[1]:
        if i%2==0 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        elif i%2==1:
            yen=yen+kabu*B[i]
    else:
        if i%2==1 and i<len(B)-1:
            kabu=yen//B[i]
            yen=yen%B[i]
        elif i%2==0:
            yen=yen+kabu*B[i]
print(yen)
import sys
input = sys.stdin.readline
from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

n,m = map(int,input().split())
A = [0]*n
B = [0]*n
C = [0]*n
for i in range(m) :
    a, b, c = map(int,input().split())
    A[i] = a-1
    B[i] = b-1
    C[i] = c

graph = [[0]*n for i in range(n)]

for i in range(m) :
    graph[A[i]][B[i]] = C[i]
    graph[B[i]][A[i]] = C[i]

graph = csgraph_from_dense(graph)
dist = dijkstra(graph)

ans = 0
for i in range(m) :
    if dist[A[i]][B[i]] != C[i] :
        ans += 1

print(ans)


### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

n,m = map(int,input().split())
edges = [[int(x) for x in input().split()] for i in range(m)]
graph = [[False]*n for i in range(n)]
for a, b, c in edges :
    graph[a-1][b-1] = c

graph = csgraph_from_dense(graph)
dist = dijkstra(graph, directed=False).astype(int)

ans = 0
for a, b, c in edges :
    if dist[a-1][b-1] != c :
        ans += 1

print(ans)
a,b,c,k = map(int,input().split())
l = [1]*a + [0]*b + [-1]*c
print(sum(l[:k])

### FIXED CODE ###

a,b,c,k = map(int,input().split())
print(min([a,k])-max([0,k-a-b]))
n = int(input())
d = list(map(int,input().split()))
mod = 998244353

if d[0] != 0:
    print(0)
    exit()

if n == 1:
    if d[0] == 0:
        print(1)
        exit()
    else:
        print(0)
        exit()

if n == 2:
    if d[1] == 1:
        print(1)
        exit()
    else:
        print(0)
        exit()


a = [0]*(n-1)

while d:
    s = d.pop()
    a[s] += 1

if a[0] >= 2:
    print(0)
    exit()

ans = 1

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

print(ans % mod)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
mod = 998244353

if d[0] != 0:
    print(0)
    exit()

if n == 1:
        print(1)
        exit()

if n == 2:
    if d[1] == 1:
        print(1)
        exit()
    else:
        print(0)
        exit()


a = [0]*n

while d:
    s = d.pop()
    a[s] += 1

if a[0] >= 2:
    print(0)
    exit()

ans = 1

for i in range(n-1):
        ans *= a[i]**a[i+1]
        ans %= mod

print(ans % mod)
x=int(input())
money=100
i=0
while true:
  money*1.01
  i+=1
  if money>=x:
    break
print i

### FIXED CODE ###

x=int(input())
total=100
years=0
while total<x:
  total*=1.01
  years+=1
  total=int(total)
print(years)
N, L = map(int, input().split())
lix = sorted(input() for i in range(L))

res = "".join(lix)
print(res)

### FIXED CODE ###

N, L = map(int, input().split())
lix = sorted(input() for i in range(N))

res = "".join(lix)
print(res)
import fractions


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    mul = a[0]
    for i in range(1, n):
        mul = mul * a[i] // fractions.gcd(mul, a[i])
    a_2 = map(lambda x: mul / x % 2, a)
    if 0 in a_2:
        print(0)
        exit()
    if m >= mul / 2:
        ans = (m - mul / 2) // mul + 1
        print(int(ans))
    else:
        print(0)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
 
def div_ceil(x, y): return (x + y - 1) // y
 
N, M = map(int, input().split())
*A, = map(int, input().split())
A = list(set([a // 2 for a in A]))
L = A[0]
for a in A[1:]:
    L *= a // gcd(L, a)
for a in A:
    if (L // a) % 2 == 0:
        ans = 0
        break
else:
    ans = div_ceil(M // L, 2)
print(ans)
n=int(input())
a=0
for i in range(1,n+1):
  for j in range(i,n+1):
    if str(i)[0]==str(j)[-1] and str(j)[0]==str(i)[-1]:
      a++
print(a)

### FIXED CODE ###

n=int(input())
t=[[0]*10 for _ in range(10)]
for i in range(1,n+1):
  t[int(str(i)[0])][i%10]+=1
a=0
for i in range(10):
  for j in range(10):
    a+=t[i][j]*t[j][i]
print(a)
N,M = map(int,input().split())
A = list(map(int,input().split()))
sortedA = sorted(A)
CB = []
for i in range(M):
    B,C = map(int,input().split())
    CB.append([C,B])

CB.sort(reverse=True)

cnt = 0
goukei = 0
flag = True
flag2 = False
for i in range(M):
    Bi,Ci = CB[i][1],CB[i][0]
    # Bi = min(Bi,N-cnt-1)
    if Bi+cnt >= N:
        Bi = N-cnt-1
        flag2 = True
            
    if sortedA[cnt+Bi] <= Ci:
        if flag2:
            cnt += Bi+1
            goukei += (Bi+1)*Ci
        else:
            cnt += Bi
            goukei += Bi*Ci
    elif sortedA[cnt] >= Ci:
        goukei += sum(sortedA[cnt:])
        flag = False
        break
    else:
        for x in sortedA[cnt:cnt+Bi+1]:
            if x <= Ci:
                goukei += Ci
            else:
                goukei += x
        goukei += sum(sortedA[cnt+Bi+1:])
        flag = False
        break
if flag:
  goukei += sum(sortedA[cnt:])

print(goukei)



### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
sortedA = sorted(A)
CB = []
for i in range(M):
    B,C = map(int,input().split())
    CB.append([C,B])

CB.sort(reverse=True)

cnt = 0
goukei = 0
flag = True
flag2 = False
for i in range(M):
    Bi,Ci = CB[i][1],CB[i][0]
    # Bi = min(Bi,N-cnt-1)
    if Bi+cnt >= N:
        Bi = N-cnt-1
        flag2 = True

    if sortedA[cnt+Bi] <= Ci:
        if flag2:
            cnt += Bi
            goukei += (Bi+1)*Ci
            flag = False
            break
        else:
            cnt += Bi
            goukei += Bi*Ci
    elif sortedA[cnt] >= Ci:
        goukei += sum(sortedA[cnt:])
        flag = False
        break
    else:
        for x in sortedA[cnt:cnt+Bi+1]:
            if x <= Ci:
                goukei += Ci
            else:
                goukei += x
        goukei += sum(sortedA[cnt+Bi+1:])
        flag = False
        break
if flag:
  goukei += sum(sortedA[cnt:])

print(goukei)
from sys import stdin, exit

N = int(stdin.readline().rstrip())
s = [int(stdin.readline().rstrip()) for _ in range(N)]
dp = [0] * (100 * N)
dp[0] = 1
for n in range(N):
    for p in range(len(dp), 0, -1):
        if dp[p - s[n]] == 1:
            dp[p] = 1
for k in range(len(dp)):
    if dp[len(dp) - k - 1] == 1 and (len(dp) - k - 1) % 10 != 0:
        print(len(dp) - k - 1)
        exit()
print('0')


### FIXED CODE ###

from sys import stdin, exit

N = int(stdin.readline().rstrip())
s = [int(stdin.readline().rstrip()) for _ in range(N)]
dp = [0] * (100 * N)
dp[0] = 1
for n in range(N):
    for p in range(len(dp) - 1, 0, -1):
        if p - s[n] >= 0:
            if dp[p - s[n]] == 1 and 0 <= p:
                dp[p] = 1
for k in range(len(dp)):
    if dp[len(dp) - k - 1] == 1 and (len(dp) - k - 1) % 10 != 0:
        print(len(dp) - k - 1)
        exit()
print('0')
A,B = map(int,input().split())

B_2 = str(bin(B)[2:])
B_2_len = len(B_2)
b_a = B-A


'''考え方
B,Aの差分が（２の倍数-1）なら、0も1も偶数個入り続ける。
Bの桁数分ループする
'''

oct = ''
for b in range(1,B_2_len+1,1):
  if b_a % (b ** 2 - 1) == 0:
    oct = '0' + oct
  else:
    oct = '1' + oct



# 2進数を１０進数に変換
out = int(oct, 2)
print(out)


### FIXED CODE ###

a, b = map(int, input().split())

def f(x):
  amari = x % 4
  if amari == 0:
    return x
  elif amari == 1:
    return x ^ (x-1)
  elif amari == 2:
    return x ^ (x-1) ^ (x-2)
  elif amari == 3:
    return 0
    
    
A = f(a-1)
B = f(b)


print(A^B)
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
v = LIST()
v.sort()
v = deque(v)
for i in range(n - 1):
    v1 = v.popleft()
    v2 = v.popleft()
    v.insert(0, (v1 + v2) / 2)
print(v[0])

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
v = LIST()
v.sort()
v = deque(v)
for i in range(n - 1):
    v1 = v.popleft()
    v2 = v.popleft()
    v.appendleft((v1 + v2) / 2)
print(v[0])
#リストAの丸太を全てx以下にK回以内の切る回数で揃えることができるかを判断する関数。
def can_or_cannot(A,K,x):
    kaisuu_sum = 0
    for i in range(len(A)):
        if A[i]%x == 0:
            temp = (A[i]//x) - 1
            kaisuu_sum += temp
        else:
            temp = A[i]//x
            kaisuu_sum += temp

        if kaisuu_sum > K:
            return 'No'

    return 'Yes'

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    #二分探索するよ
    left = 0
    right = A[N-1]
    mid = 0
    while True:
        mid = int( (left + right)/2 )
        #print(left,mid,right)
        judge = can_or_cannot(A,K,mid)
        #print(left,mid,right,judge)
        if judge == 'No':
            left = mid+1
        elif judge == 'Yes':
            right = mid

        if left == right:
            #print(left,mid,right)
            return right

print(main())


### FIXED CODE ###

#リストAの丸太を全てx以下にK回以内の切る回数で揃えることができるかを判断する関数。
def can_or_cannot(A,K,x):
    kaisuu_sum = 0
    for i in range(len(A)):
        if A[i]%x == 0:
            temp = (A[i]//x) - 1
            kaisuu_sum += temp
        else:
            temp = A[i]//x
            kaisuu_sum += temp

        if kaisuu_sum > K:
            return 'No'

    return 'Yes'

def main():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    #二分探索するよ
    left = 0
    right = A[N-1]

    if right == 1:
        return 1

    mid = 0
    while True:
        if right == 1:
            return 1
            
        mid = int( (left + right)/2 )
        #print(left,mid,right)
        judge = can_or_cannot(A,K,mid)
        #print(left,mid,right,judge)
        if judge == 'No':
            left = mid+1
        elif judge == 'Yes':
            right = mid

        if left == right:
            #print(left,mid,right)
            return right

print(main())
N=int(input())
mod=10**9+7
Azero=0
Bzero=0
both=0
plus={}
minus={}
import math
for i in range(N):
  A,B=map(int,input().split())
  if A==0 and B==0:
    both+=1
  elif A==0 and B!=0:
    Azero+=1
  elif A!=0 and B==0:
    Bzero+=1
  else:
    K=math.gcd(A,B)
    A=int(A/K)
    B=int(B/K)
    if A/B>0:
      if A<0:
        A,B=-A,-B
      if (A,B) in plus:
        plus[(A,B)]+=1
      else:
        plus[(A,B)]=1
    else:
      if A<0:
        A,B=-A,-B
      if (A,B) in minus:
        minus[(A,B)]+=1
      else:
        minus[(A,B)]=1

L=[]
if Azero>0 and Bzero>0:
  L.append((Azero,Bzero))
for k,v in plus.items():
  if (k[1],-k[0]) in minus:
    L.append((v,minus[(k[1],-k[0])]))
ans=0
for i in range(len(L)):
  N-=L[i][0]+L[i][1]
N-=both
c=1

for i in range(len(L)):
  c*=(pow(2,L[i][0],mod)+pow(2,L[i][1],mod)-1)
  c%=mod

ans=(c*pow(2,N,mod)-1)%mod

print(ans+both)

### FIXED CODE ###

N,M=map(int,input().split())
g=[[] for _ in range(N)]
for i in range(M):
  A,B=map(int,input().split())
  g[A-1].append(B-1)
  g[B-1].append(A-1)
from collections import deque  
queue = deque([0])
d = [None] * N
d[0] = 0 
while queue:
  v = queue.popleft()
  for i in g[v]:
    if d[i] is None:
      d[i] = d[v] + 1
      queue.append(i)
  
l=[0]*(N-1)
for i in range(1,N):
  for j in g[i]:
    if d[j]==(d[i]-1):
      l[i-1]=j+1
      break
if 0 in l:
  print('No')
else:
  print('Yes')
  for i in range(len(l)):
    print(l[i])
N,Y = input().split()
N = int(N)
Y_k=int(Y)/1000

answer - [-1,-1,-1]
for i in range(N+1):
    for j in range(N+1 - i):
        k = N-i-j
        if 10*i + 5*j + 1*k == Y_k:
            answer = [i,j,k]

print(answer[0],answer[1],answer[2])


### FIXED CODE ###

N,Y = input().split()
N = int(N)
Y_k=int(Y)/1000

answer = [-1,-1,-1]
for i in range(N+1):
    for j in range(N+1 - i):
        k = N-i-j
        if 10*i + 5*j + 1*k == Y_k:
            answer = [i,j,k]

print(answer[0],answer[1],answer[2])