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

#input()を速い方にしないとTLEになる

import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
input = sys.stdin.readline

def dfs(v,p): #点vについての処理。p：vの親
    if (p != -1): res[v] += res[p]
    
    for e in edges[v]:
        if (e == p): continue
        dfs(e,v)
#--------------------------------
N, Q = map(int, input().split())
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

px = [list(map(int, input().split())) for _ in range(Q)]

res = [0]*(N+1) #点数リスト
for i in range(Q): #点数リストに初期値を格納
    p,x = px[i]
    res[p] += x

dfs(1,-1)
print(*res[1:])


### FIXED CODE ###

import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,Q = LI()
ab = [LI() for _ in [None]*(N-1)]
px = [LI() for _ in [None]*(Q)]
ans = [0]*(N+1) #1_index
graph = [collections.deque() for _ in [None]*(N+1)] #1_index
for a,b in ab:
        graph[a].append(b)
        graph[b].append(a)
for p,x in px:
    ans[p] += x
seen = [0]*(N+1) #1_index
stack = []
def dfs():
    seen[1] = 1
    stack.append(1)
    while stack:
        s = stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            g_NO = graph[s].popleft()
            if seen[g_NO]:
                continue
            seen[g_NO] = 1
            stack.append(g_NO)
            ans[g_NO] += ans[s]
dfs()
print(*ans[1:])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, Q: int, A: "List[int]"):
    human = np.full(N, K)

    for i in range(Q):
        ind = np.ones(N, dtype=bool)
        ind[A[i]-1] = False
        human[ind] = human[ind] - 1
        ind[A[i]-1] = True
        
    for j in range(N):
   
        if human[j] > 0:
            print(YES)
        else:
            print(NO)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, K, Q, A)

if __name__ == '__main__':
    main()




### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int, K: int, Q: int, A: "List[int]"):
    human = np.full(N, K)
    score = np.zeros(N)
    #print(human)
    for i in range(Q):
        #print("i =", i)
        # ind = np.ones(N, dtype=bool)
        # ind[A[i]-1] = False
        # human[ind] = human[ind] - 1
        # ind[A[i]-1] = True
        #human[A[i]-1] += 1
        #print('human =', human)
        score[A[i]-1] += 1

    human = human - Q + score

    #print(human)
    human2 = list(map(lambda x: YES if x > 0 else NO, human))
    print('\n'.join(human2))
    '''
    for j in range(N):
        #print(j, human[j])
        if human[j] > 0:
            print(YES)
        else:
            print(NO)
    '''
    return
    

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(Q)]  # type: "List[int]"
    solve(N, K, Q, A)

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

K_S = input().split(" ")
ans = 0
for X in range(int(K_S[0]) + 1):
    for Y in range(int(K_S[0]) + 1):
        Z = int((K_S[1])) - X - Y
        if 0 <= Z & Z <= int(K_S[0]):
            ans += 1

print(ans)
    

### FIXED CODE ###

K_S = input().split()
ans = 0
for X in range(int(K_S[0]) + 1):
    for Y in range(int(K_S[0]) + 1):
        Z = int((K_S[1])) - X - Y
        if 0 <= Z & Z <= int(K_S[0]):
            ans += 1

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

#!/usr/bin/env python
from math import sqrt

def gen_primes(X):
    is_prime = [True for _ in range(0, X+1)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for n in range(2, int(sqrt(X))):
        if is_prime[n]:
            primes.append(n)
            j = n*2
            while j <= X:
                is_prime[j] = False
                j += n
    primes.extend([x for x in range(int(sqrt(X)), X+1) if is_prime[x]])
    return primes


def solve(N, A):
    primes = gen_primes(10**6)
    C = [0] * len(primes)

    for a in A:
        for i, p in enumerate(primes):
            if a % p == 0:
                C[i] += 1
    M = max(C)
    #print(A)
    #print(M)
    if M <= 1:
        print("pairwise coprime")
    elif M != N:
        print("setwise coprime")
    else:
        print("not coprime")
    
N = int(input())
A = [int(x) for x in input().split()]
solve(N, A)


### FIXED CODE ###

#!/usr/bin/env python
from math import sqrt
from collections import Counter

def gen_primes(X):
    D = [0] * (X+1)
    is_prime = [True for _ in range(0, X+1)]
    is_prime[0] = False
    is_prime[1] = False
    primes = []
    for n in range(2, int(sqrt(X))+1):
        if is_prime[n]:
            primes.append(n)
            j = n*2
            D[n] = n
            while j <= X:
                is_prime[j] = False
                if D[j] == 0:
                    D[j] = n
                j += n
    for n in range(int(sqrt(X)), X+1):
        if is_prime[n]:
            D[n] = n
            primes.append(n)
    return primes, D


def solve(A):
    N = len(A)
    primes, D = gen_primes(10**6)
    C = [0] * (primes[-1]+1)

    for a in A:
        a_ = a
        while a > 1:
            d = D[a]
            while a % d == 0:
                a //= d
            C[d] += 1
        
    M = max(C)
    if M <= 1:
        print("pairwise coprime")
    elif M != N:
        print("setwise coprime")
    else:
        print("not coprime")

#solve([x for x in range(1, 10**6+1)])
N = int(input())
A = [int(x) for x in input().split()]
solve(A)
### BUGGY CODE ###

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

    su = [0 for _ in range(n + 1)]    
    for i in range(n):
        su[i + 1] = su[i] + a[i]

    INF = 1e18
    dp = [[-INF for _ in range(n + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][i] = 0

    for length in range(1, n + 1):
        i = 0
        while i + length <= n:
            j = i + length
            dp[i][j] = max(a[i] + (su[j] - su[i + 1]) - dp[i + 1][j], a[j - 1] + (su[j - 1] - su[i]) - dp[i][j - 1])
            i += 1
    
    print(dp[0][n] - (su[n] - dp[0][n]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

    su = [0 for _ in range(n + 1)]    
    for i in range(n):
        su[i + 1] = su[i] + a[i]

    INF = 1e18
    dp = [[-INF for _ in range(n + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][i] = 0

    for length in range(1, n + 1):
        i = 0
        while i + length <= n:
            j = i + length
            dp[i][j] = max(a[i] + (su[j] - su[i + 1]) - dp[i + 1][j], a[j - 1] + (su[j - 1] - su[i]) - dp[i][j - 1])
            i += 1
    
    print(dp[0][n] - (su[n] - dp[0][n]))

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

def search(ind):
    for i in range(ind):
        if p_ls[i] < p_ls[ind]:
            return 0
    return 1

n = int(input())
p_ls = list(map(int, input().split()))
sub_cnt = 0
one = p_ls.index(1)+1
for i in range(one):
    sub_cnt += search(i)
print(sub_cnt)


### FIXED CODE ###

n = int(input())
p_ls = list(map(int, input().split()))
mini = p_ls[0]
cnt = 0
for i in range(n):
    if mini >= p_ls[i]:
        cnt+=1
        mini= p_ls[i]
print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
numlist = []
for i in range(M):
    B, C = map(int, input().split())
    numlist.append([C, B])
for i in range(N):
    numlist.append([A[i], 1])
numlist.sort(reverse = True)
count = N
ans = 0
while count >= 0:
    b, c = numlist.pop(0)
    if c <= count:
        ans += b * c
    else:
        ans += b * count
    count -= c
print(ans)



### FIXED CODE ###


N, M = map(int, input().split())
A = list(map(int, input().split()))
num = dict()
for i in range(M):
    B, C = map(int, input().split())
    if C in num.keys():
        num[C] += B
    else:
        num[C] = B
for i in range(N):
    if A[i] in num.keys():
        num[A[i]] += 1
    else:
        num[A[i]] = 1
dct = sorted(num.items(), reverse = True)
count = N
ans = 0
for i in range(len(dct)):
    b, c = dct[i]
    if c <= count:
        ans += b * c
    else:
        ans += b * count
    count -= c
    if count <= 0:
        break
print(ans)
### BUGGY CODE ###

def q4():
    N, K = (int(i) for i in input().split())
    P = [int(i) for i in input().split()]
    # pが大きいほど、期待値も大きくなる
    max_sum = 0
    max_pos = 0
    for i in range(0, N-K+1):
        s = sum(P[i:(i+K)])
        if max_sum < s:
            max_sum = s
            max_pos = i

    ans = 0
    for p in P[max_pos:(max_pos + K)]:
        s = sum([i for i in range(1,p+1)]) / p
        ans += s
    print('{0:.7f}'.format(ans))

if __name__ == '__main__':
    q4()

### FIXED CODE ###

def q4():
    from itertools import accumulate

    N, K = (int(i) for i in input().split())
    P = [int(i) for i in input().split()]

    P_kitai = [0]
    # 整数1からNまでの合計は、sum = N(N+1)/2
    # 期待値は sum / N より、(N+1)/2 で表される。
    for p in P:
        P_kitai.append((p+1)/2)
    accu = list(accumulate(P_kitai))
    #print(accu)
    max_sum = 0
    for i in range(0, N-K+2):
        max_sum = max(max_sum, accu[i+K-1] - accu[i-1])
    print(max_sum)

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

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

for x in range(n):
    if x!=a.index(max(a)):
            print(max(a))
    else:
            print(sorted(a)[-2])


### FIXED CODE ###

n=int(input())
a=[int(input()) for i in range(n)]
Max=max(a)
Second=sorted(a)[-2]
Index=a.index(Second)
[print(Max) if i!=Max else print(Second) for i in a]
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
i=0
lst = []
x = set()
while i < m: 
    l = list(map(int, input().split()))
    l.append(i)
    x.add(l[0])
    lst.append(l)
    i+=1
ll=sorted(lst)
j=1
for i in sorted(list(x)):
    for k in ll:
        if i > k[0]:
            continue
        if i == k[0]:
            k[1]=i*1000000+j
            j+=1
        else:
            j=1
            break


#ans
for ans in sorted(ll, key=lambda x:x[2]):
    print('{0:012d}'.format(ans[1]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
n,m = map(int, input().split())
i=0
lst = []
while i < m: 
    lst.append(list(map(int, input().split())) + [i])
    i+=1
lst = sorted(lst)
j=0
i=1
for k in lst:
    if i != k[0]:
        i=k[0]
        j=1
        k[1]=i*1000000+j
    else:
        j+=1
        k[1]=i*1000000+j

#ans
for ans in sorted(lst, key=lambda x:x[2]):
    print('{0:012d}'.format(ans[1]))
### BUGGY CODE ###

import sys
check=dict()
N,b,d=0,[],0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d

    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d

    x1,x2=n//ttf,n%ttf
    if ttf-x2>=x2:
        if x1==0:
            if x1 in check:
                if check[x1]>check[n]+x2*d:
                    check[x1]=check[n]+x2*d
            else:
                check[x1]=check[n]+x2*d
        else:
            if x1 in check:
                if check[x1]>check[n]+x2*d+cha:
                    check[x1]=check[n]+x2*d+cha
                    dfs(x1)
            else:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)

    x1,x2=n//ttf+1,ttf-n%ttf
    if ttf-x2>=x2:
        if x1 in check:
            if check[x1]>check[n]+x2*d+cha:
                check[x1]=check[n]+x2*d+cha
                dfs(x1)
        else:
            check[x1]=check[n]+x2*d+cha
            dfs(x1)


def dfs(n):
    global b,check,d
    for i,j in zip([2,3,5],b):
        dfs_sub(n,i,j)

t=int(input())
for i in range(t):
    N,*b,d=map(int,input().split())
    check={N:0}
    dfs(N)
    print(check[0])

### FIXED CODE ###

import sys
check=dict()
N,a,b,c,d=0,0,0,0,0
#ttfは235、chaはabc
def dfs_sub(n,ttf,cha):
    global check,d
    if 0 in check:
        check[0]=min(check[n]+n*d,check[0])
    else:
        check[0]=check[n]+n*d
    if n//ttf==0:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d:
                check[n//ttf]=check[n]+(n%ttf)*d
        else:
            check[n//ttf]=check[n]+(n%ttf)*d
    else:
        if n//ttf in check:
            if check[n//ttf]>check[n]+(n%ttf)*d+cha:
                check[n//ttf]=check[n]+(n%ttf)*d+cha
                dfs(n//ttf)
        else:
            check[n//ttf]=check[n]+(n%ttf)*d+cha
            dfs(n//ttf)
    if 1+n//ttf in check:
        if check[1+n//ttf]>check[n]+(ttf-n%ttf)*d+cha:
            check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
            dfs(1+n//ttf)
    else:
        check[1+n//ttf]=check[n]+(ttf-n%ttf)*d+cha
        dfs(1+n//ttf)


def dfs(n):
    global check,a,b,c,d
    dfs_sub(n,2,a)
    dfs_sub(n,3,b)
    dfs_sub(n,5,c)

t=int(input())
ans=[0]*t
for i in range(t):
    N,a,b,c,d=map(int,input().split())
    check={N:0}
    dfs(N)
    ans[i]=check[0]
for i in range(t):
    print(ans[i])
### BUGGY CODE ###

from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
 
 
 
print(ans)

### FIXED CODE ###

from collections import deque
H,W=map(int, input().split())
 
A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0
 
d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)
 
 
 
print(ans)
### BUGGY CODE ###

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

Buka_list = []
i = 1
while 1:
    ninzu = A_list.count(i)
    print(ninzu)
    i += 1
    if i > N:
        break

### FIXED CODE ###

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

Buka_list = []

for i in range(N):
    Buka_list.append(0)
    
for j in A_list:
    Buka_list[j-1] += 1

for k in range(N):
    print(Buka_list[k])
### BUGGY CODE ###

# 解説放送

def main():
    N, K = map(int, input().split())
    *P, = (int(x) - 1 for x in input().split())
    *C, = map(int, input().split())

    ans = -10**9 - 1

    for si in range(N):
        g = []
        tot = 0
        cur = si
        while True:
            cur = P[cur]
            g.append(C[cur])
            tot += C[cur]
            if cur == si or len(g) == K:
                break

        L = len(g)
        t = 0
        for i, x in enumerate(g, start=1):
            t += x
            now = t
            if tot > 0:
                rep = (K - i) // L
                now += tot * rep

            ans = max(ans, now)

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# 解説放送

def main():
    N, K = map(int, input().split())
    *P, = (int(x) - 1 for x in input().split())
    *C, = map(int, input().split())

    ans = -10**9 - 1

    for si in range(N):
        g = []
        tot = 0
        cur = si
        while True:
            cur = P[cur]
            g.append(C[cur])
            tot += C[cur]
            if cur == si or len(g) == K:
                break

        L = len(g)
        t = 0
        for i, x in enumerate(g, start=1):
            t += x
            now = t
            if tot > 0:
                rep = (K - i) // L
                now += tot * rep

            ans = max(ans, now)

    print(ans)


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

import sys
read = sys.stdin.buffer.read

n,*X=map(int,read().split())
mod = 10**9+7
last=X[-1]
X=[last-i for i in X[:-1]]
l=1
left=[1]
for i in range(1, n-1):
  l=l*i
  left.append(l)
r=1
right=[1]
for i in range(n-1, 1, -1):
  r*=i
  right.append(r)
right.reverse()
flst=[i*j for i,j in zip(left,right)]
s = sum(i*j%mod for i,j in zip(X,flst))
print(s%mod)

### FIXED CODE ###

# https://atcoder.jp/contests/dwacon6th-prelims/submissions/9426910


def solve():
    MOD = 10**9 + 7

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

    ds = []
    for i in range(N-1):
        d = xs[i+1] - xs[i]
        ds.append(d)

    nums = [1, 1]
    num = 1
    for i in range(2, N-1):
        num *= i
        num %= MOD
        nums.append(num)

    ms = [N-1]
    m = N-1
    for i in reversed(range(2, N-1)):
        m *= i
        m %= MOD
        ms.append(m)
    ms.reverse()
    ms.append(1)

    ks = []
    k = 0
    for num, m in zip(nums, ms):
        k += num*m % MOD
        k %= MOD
        ks.append(k)

    ans = 0
    for d, k in zip(ds, ks):
        ans += d*k % MOD
        ans %= MOD

    print(ans)

solve()
### BUGGY CODE ###

n = int(input())
if n == 1:
    print(0)
else:
    a=[i for i in range(1,n+1)]
    b=[i for i in range(2,n+1)]+[1]
    print(sum([a[i] % b[i] for i in range(n)]))

### FIXED CODE ###

n = int(input())
m = n - 1
print(m*(m+1)//2)
### BUGGY CODE ###

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

def gcd(x, y):
    if x < y: x, y = y, x
    while y != 0:
        x, y = y, x % y
    return x

gcd_ab = gcd(a, b)
if gcd_ab == 1:
    print(1)
    exit()

def get_divisor(n):
    divisor = {}
    while n % 2 == 0:
        divisor[2] = 1
        # if 2 in divisor:
        #     divisor[2] += 1
        # else:
        #     divisor[2] = 1
        # n //= 2

    i = 3
    while i <= n:
        while n % i == 0:
            if i in divisor:
                divisor[i] += 1
            else:
                divisor[i] = 1
            n //= i
        i += 2
    return divisor

divisor = get_divisor(gcd_ab)
print(len(divisor)+1)




### FIXED CODE ###

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

from fractions import gcd
from collections import Counter
# def gcd(x, y):
#     if x < y: x, y = y, x
#     while y != 0:
#         x, y = y, x % y
#     return x

gcd_ab = gcd(a, b)
if gcd_ab == 1:
    print(1)
    exit()

def get_divisor(n):
    divisor = Counter()
    while n % 2 == 0:
        divisor[2] += 1
        n //= 2
        
    i = 3
    while i*i <= n:
        while n % i == 0:
            divisor[i] += 1
            n //= i
        i += 2
    if n > 1:
        divisor[n] += 1
    return divisor

divisor = get_divisor(gcd_ab)
print(len(divisor)+1)
### BUGGY CODE ###

def main():
    mod = 10 ** 9 + 7

    K = map(int, list(input()))
    D = int(input())

    s = 0
    dp = [0] * D
    for k in K:
        T = [0] * D
        for i, dpi in enumerate(dp):
            for x in range(10):
                T[(i + x) % D] += dpi
                T[(i + x) % D] % mod
        for x in range(k):
            T[(s + x) % D] += 1

        s = (s + k) % D
        dp = T

    print((dp[0] + (-1 if s != 0 else 0)) % mod)

main()

### FIXED CODE ###

mod = 10 ** 9 + 7

K = input()
D = int(input())

s = 0
dp = [0] * D
for k in K:
    k = int(k)

    T = [0] * D
    for i, dpi in enumerate(dp):
        for x in range(10):
            T[(i + x) % D] = (T[(i + x) % D] + dpi) % mod
    for x in range(k):
        T[(s + x) % D] += 1

    s = (s + k) % D
    dp = T

print((dp[0] + (-1 if s != 0 else 0)) % mod)
### BUGGY CODE ###

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

ans = sum(a)
b = a[:]
c = [0]*n

for k in range(1, n):
	now = k * x
	for i in range(n):
		tmp = min(b[i-1], a[i])
		now += tmp
		c[i] = tmp
	ans = min(ans, now)
	b = c[:]
	
print(ans)

### FIXED CODE ###

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

ans = sum(a)
b = a[:]
c = [0]*n

for k in range(1, n):
	now = k * x
	for i in range(n):
		tmp = min(b[i-1], a[i])
		now += tmp
		c[i] = tmp
	ans = min(ans, now)
	b = c[:]
	
print(ans)
### BUGGY CODE ###

s = input()
k = int(input())
li = []
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        li += [s[i:j]]
li2 = set(li)
li3 = sorted(li2)
print(li3[k-1])

### FIXED CODE ###

s = input()
k = int(input())
li = []
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        if j-i<=6:
            li += [s[i:j]]
li2 = set(li)
li3 = sorted(li2)
print(li3[k-1])
### BUGGY CODE ###

n =int(input())
ls = []

if n%2==0:
    for i,j in enumerate(input().split()):
        if i%2==0:
            ls.append(j)
        else:
            ls.insert(0,j)
else:
    for i,j in enumerate(input().split()):
        if i%2==1:
            ls.append(j)
        else:
            ls.insert(0,j)

print(" ".join(ls))

### FIXED CODE ###

n =int(input())
a = list(map(str,input().split()))
lss = []
lse = []
if n%2==0:
    for i in range(n//2):
        lss.append(a[2*i])
    for i in range(n//2):
        lse.append(a[n-(2*i+1)])

else:
    for i in range(n//2):
        lss.append(a[2*i+1])
    for i in range(n//2+1):
        lse.append(a[n-2*i-1])


ls = lse+lss

print(" ".join(ls))
### BUGGY CODE ###

import scipy.misc as scm
def comb(k,r):
  """kCpを求める"""
  if k<0 or r<0 or r>k: return 0
  elif k==0 or r==0: return 1
  else:
    return (X[k]*Y[r]*Y[k-r])
  
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
n = int(input())
a = list(map(int,input().split()))
p=10**9+7
ans=0
X=[1]  #階乗テーブル
for i in range(1,n+2):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(n+2)  #階乗の逆元テーブル
Y[n+1]=power_func(X[n+1],p-2,p)
for i in range(n,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p

#ダブりをみつける
check = [0]*n
for i in range(n+1):
  if check[a[i]-1]==1: dub = a[i]
  else: check[a[i]-1] = 1

indexes = [i for i, x in enumerate(a) if x == dub]
ind1, ind2  = indexes[0], indexes[1]

for i in range(1,n+2):
  ans = scm.comb(n+1, i,1)
  if ind1 + n -ind2 +1 >= i:
    ans -= scm.comb(ind1 + n -ind2, i-1,1)
  print(ans%p)

### FIXED CODE ###

def comb(k,r):
  """kCpを求める"""
  if k<0 or r<0 or r>k: return 0
  elif k==0 or r==0: return 1
  else:
    return (X[k]*Y[r]*Y[k-r])
  
def power_func(a,b,p):
  """a^b mod p を求める"""
  if b==0: return 1
  if b%2==0:
    d=power_func(a,b//2,p)
    return d*d %p
  if b%2==1:
    return (a*power_func(a,b-1,p ))%p
n = int(input())
a = list(map(int,input().split()))
p=10**9+7
ans=0
X=[1]  #階乗テーブル
for i in range(1,n+2):
  X+=[ (X[-1]*i) %p ]
Y=[1]*(n+2)  #階乗の逆元テーブル
Y[n+1]=power_func(X[n+1],p-2,p)
for i in range(n,-1,-1):
  Y[i]=Y[i+1]*(i+1) %p

#ダブりをみつける
check = [0]*n
for i in range(n+1):
  if check[a[i]-1]==1: dub = a[i]
  else: check[a[i]-1] = 1

indexes = [i for i, x in enumerate(a) if x == dub]
ind1, ind2  = indexes[0], indexes[1]

for i in range(1,n+2):
  ans = comb(n+1, i)
  if ind1 + n -ind2 +1 >= i:
    ans -= comb(ind1 + n -ind2, i-1)
  print(ans%p)