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

import copy
import sys

sys.setrecursionlimit(200000000)

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

def dfs(string, root):
    temps = [i+1 for i in range(len(string))]
    output=-1
    if len(string)==0:
        return root
    
    for i,s in enumerate(string):
        if i+1==s:
            temp_root = copy.deepcopy(root)
            temp_string=copy.deepcopy(string)
            temp_root.append(i+1)
            temp_string.pop(i)
            temp = dfs(temp_string, temp_root)
            
            if temp!=-1:
                output=temp
                break
    return output

output=dfs(a, [])

output

if isinstance(output, list):
    for i in output[::-1]:
        print(i)
else:
    print(output)

### FIXED CODE ###

import copy

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


root=[]
string = copy.deepcopy(a)
while len(string)!=0:
    temp=[]
    for i,s in enumerate(string):
        if i+1 == s:
            temp.append(i+1)
    if len(temp)==0:
        break
    
    if temp[0]==1 and len(temp)==1:
        string.pop(0)
        root.append(1)
    else:
        if 1 in temp:
            temp.remove(1)
        root.append(temp[-1])
        string.pop(temp[-1]-1)
        
if len(string)!=0:
    print(-1)
else:
    for i in root[::-1]:
        print(i)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
list = []
for i in range(Q):
    l,r = map(int, input().split())
    list.append([l,r])

#print(list)

target_s = 'AC'
for i in range(Q):
    sub_S = S[list[i][0]-1:list[i][1]]

    '''
    #print(i,sub_S)
    count = 0
    for j in range(len(sub_S)+1-len(target_s)):
        sub_sub_S = sub_S[j:j+len(target_s)]
        #print(sub_sub_S)
        if sub_sub_S == target_s:
            count += 1
    '''

    print(sub_S.count(target_s))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
list = [[0 for i in range(2)] for j in range(Q)]

b = [0] * (N+1)
for i in range(N):
    if S[i:i+2] == 'AC':
        b[i+1] = b[i] + 1
    else:
        b[i+1] = b[i]
for i in range(Q):
    l,r = map(int, input().split())
    print(b[r-1]-b[l-1])
### BUGGY CODE ###

#AGC030 B - Powers of two
beki=[]
for i in range(1,32):
    beki.append(2**i)#bekiは２のべき乗の配列
N=int(input())
A=input().split()
ans=0
for i in range(N):
    A[i]=int(A[i])
for j in (reversed(beki)):
    for k in range(N):
        for l in range(k):
            if A[k]*A[l]!=0 and A[k]+A[l]==j:
                A[k]=0
                A[l]=0
                ans=ans+1
print(ans)

### FIXED CODE ###

#AGC030 B - Powers of two
import collections
import math
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
cnter=collections.Counter(A)
ans=0
for a in A:
    inv=2**(int(math.log2(a))+1)
    if cnter[a]==0:
        continue
    if inv==2*a and cnter[inv-a]<=1:
      	continue
    if cnter[inv-a]>0:
        cnter[inv-a]=cnter[inv-a]-1
        cnter[a]=cnter[a]-1
        ans=ans+1
print(ans)
### BUGGY CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

S = input()

def solve(S):
    L = len(S)

    tmp = 0
    tmpS = ''
    for i in range(L):
        if S[i] == '1':
            tmpS = S[i+1:]
            tmp =  L - 1 - i
            break
    else:
        return 1

    return (2*solve(tmpS) + solve_bin(tmp))%mod

def solve_bin(b):
    return pow(3,b,mod)

print(solve(S)%mod)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7

def solve(l):
    tmp = 0
    tmpS = ''
    for i in range(l,L):
        if S[i] == '1':
            return (2*solve(i+1) + pow(3,L-1-i,mod))%mod
    else:
        return 1

S = input()
L = len(S)
print(solve(0)%mod)
### BUGGY CODE ###

N = int(input())
A_list = list(map(int,input().split()))
cnt = 0
for i in range(1,N):
    for j in range(i+1, N+1):
        if A_list[i-1] * A_list[j-1] >= 10**9 + 7:
            cnt += (A_list[i-1] * A_list[j-1]) % (10**9 + 7) 
        else:
            cnt += A_list[i-1] * A_list[j-1]
        if cnt >= (10**9 + 7):
            cnt %= (10**9 + 7)
print(cnt)

### FIXED CODE ###

from itertools import accumulate
N = int(input())
A_list = list(map(int,input().split()))
B_list = A_list[::-1]
C_list = list(accumulate(B_list))
D_list = C_list[::-1]
cnt = 0
for i in range(1,N):
    cnt += (A_list[i-1] * D_list[i]) % (10**9 + 7)

    if cnt >= (10**9 + 7):
        cnt -= (10**9 + 7)
print(cnt)
### BUGGY CODE ###

import sys
from heapq import heappush, heappop, heapify
n = int(input())
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]
result = 0
finished = 0
for i in range(n):
  if a[i] == b[i]:
    finished += 1
hq = [(-b[i], i) for i in range(n) if a[i] != b[i]]
heapify(hq)
while True:
  _, i = heappop(hq)
  if i == 0:
    b[i] -= b[n - 1] + b[1]
  elif i == n -1:
    b[i] -= b[n - 2] + b[0]
  else:
    b[i] -= b[i - 1] + b[i + 1]
  if a[i] > b[i]:
    print(-1)
    sys.exit()
  result += 1
  if a[i] == b[i]:
    finished += 1
    if finished == n:
      print(result)
      sys.exit()
  else:
    heappush(hq, (-b[i], i))


### FIXED CODE ###

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i] - a[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()
### BUGGY CODE ###

n, w = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

# 最大化問題なので0で初期化
dp = [[0] * (w + 1) for _ in range(n + 1)]

# 品物iを選ばない場合で更新してから、選べる場合は再更新
for i in range(1, n + 1):
    for j in range(w + 1):
        dp[i][j] = dp[i - 1][j]
        if j - arr[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1])

print(dp[n][w])

### FIXED CODE ###

n, w = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

# 最大化問題なので0で初期化
dp = [[0] * (w + 1) for _ in range(n + 1)]

# 品物iを選ばない場合で更新してから、選べる場合は再更新
for i in range(1, n + 1):
    for j in range(w + 1):
        dp[i][j] = dp[i - 1][j]
        if j - arr[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1])

print(dp[n][w])
### BUGGY CODE ###

n=int(input())
m=max(n,2)+1
while 1:
    if m%2 and m%n:
        print(m)
    m+=1

### FIXED CODE ###

n=int(input())
print(n*(1+n%2))
### BUGGY CODE ###

def LCS(S,T):
  #初期化
  dp=[[0 for i in range(len(T)+1)] for j in range(len(S)+1)]

  #DP
  for i in range(len(S)):
    for j in range(len(T)):
      dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j])
      if S[i]==T[j]:
        dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+1)
  return dp[len(S)][len(T)]

N = int(input())
St = input()
ans = 0
for i in range(1,N):
  S = St[:i]
  T = St[i:]
  ans = max(LCS(S,T), ans)
        
        
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
from collections import deque

def is_ok(l):
    hs = set()
    q = deque()
    for i in range(N-l+1):
        h = S[i:i+l]
        if h in hs:
            return True
        q.append(h)
        if len(q) >= l:
            hs.add(q.popleft())
    return False

ok = 0
ng = N//2+1
while ng-ok > 1:
    m = (ng+ok)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)
### BUGGY CODE ###

def main():
    s = [input() for l in range(2)]
    N, A_dct, A = int(s[0]), {int(x): int(x) for x in s[1].split()}, [int(x) for x in s[1].split()]
    if 0 in A_dct:
        print(0)
    else:
        tmp = 1
        for k in A:
            tmp *= k
        if tmp > 10**18: tmp = -1
        print(tmp)
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    s = [input() for l in range(2)]
    N, A_dct, A = int(s[0]), {int(x): int(x) for x in s[1].split()}, [int(x) for x in s[1].split()]
    if 0 in A_dct:
        print(0)
    else:
        tmp = 1
        for k in A:
            tmp *= k
            if tmp > 10**18:
                tmp = -1
                break
        print(tmp)
    

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

def comb(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%MOD

MOD=10**9+7
MAXN=2000000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+1):
    g1.append((g1[-1]*i)%MOD)
    inverse.append(-inverse[MOD%i]*(MOD//i)%MOD)
    g2.append((g2[-1]*inverse[-1])%MOD)

r1, c1, r2, c2=map(int, input().split())
s1=comb(r2+c2+2, r2+1)
s2=comb(r1+c2+1, r1)
s3=comb(r2+c1+1, r2+1)
s4=comb(r1+c1, r1)
print(s1-s2-s3+s4)


### FIXED CODE ###

def comb(n, r):
    if r<0 or r>n:
        return 0
    r=min(r, n-r)
    return g1[n]*g2[r]*g2[n-r]%MOD

MOD=10**9+7
MAXN=2000000+10
g1=[1, 1]
g2=[1, 1]
inverse=[0, 1]

for i in range(2, MAXN+1):
    g1.append((g1[-1]*i)%MOD)
    inverse.append(-inverse[MOD%i]*(MOD//i)%MOD)
    g2.append((g2[-1]*inverse[-1])%MOD)

r1, c1, r2, c2=map(int, input().split())
s1=comb(r2+c2+2, r2+1)-1
s2=comb(r1+c2+1, r1)-1
s3=comb(r2+c1+1, r2+1)-1
s4=comb(r1+c1, r1)-1
print((s1-s2-s3+s4)%MOD)
### BUGGY CODE ###

N = int(input())
S = input()

ans = 0
k = 'RGB'
for i in range(N):
	for j in range(i+1,N):
		if not S[i]==S[j]:
			tmp =k.replace(S[i],'')
			tmp = tmp.replace(S[j],'')
			ans += S[j+1:].count(tmp)
			if 2*j-i<N and S[2*j-i]==tmp:
				ans -= 1
print(ans)


### FIXED CODE ###

import sys
from collections import defaultdict
d = defaultdict(str)
N = int(sys.stdin.readline())
S = sys.stdin.readline()

ans = 0
k = 'RGB'
for i in range(N):
	for j in range(i+1,N):
		if not S[i]==S[j]:
			tmp =k.replace(S[i],'')
			tmp = tmp.replace(S[j],'')
			if d[str(j+1)+tmp]=='':
				p = S[j+1:].count(tmp)
				d[str(j+1)+tmp] = p
				ans += p
				if 2*j-i<N and S[2*j-i]==tmp:
					ans-= 1
					
			else:
				ans +=d[str(j+1)+tmp]
				if 2*j-i<N and S[2*j-i]==tmp:
					ans -=1
print(ans)
### BUGGY CODE ###

import math
r,g,b,n = map(int, input().split())
count = 0
r,g,b = sorted((r,g,b))
for x in range( math.ceil((n / r)) + 1):
    for y in range( math.ceil( (n - (r*x) ) / g) + 1):
        for z in range(math.ceil((n - (r * x) - (g * y)) + 1)):
            if (n - (r * x) - (g * y) - (b * z) ) == 0:
                count = count + 1
print(count)

### FIXED CODE ###

import math
r,g,b,n = map(int, input().split())
count = 0
r,g,b = sorted((r,g,b), reverse=True)
for x in range( math.ceil((n / r)) + 1):
    for y in range( math.ceil( (n - (r*x) ) / g) + 1):
        if (n - (r*x) - (y*g)) < 0:
            break
        if ((n - (r*x) - (g * y)) % b) == 0:
            count = count + 1
print(count)
### BUGGY CODE ###

# S=input()
S="".join(["1" for _ in range(10**4)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    tt = 10**t
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (t,(j*tt+i)%13)
                dp[k] += dp[(t-1,i)]
                dp[k] %= MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (t,(s*tt+i)%13)
            dp[k] += dp[(t-1,i)]
            dp[k] %= MOD

print(dp[(t,5)])

### FIXED CODE ###

S=input()
# S="".join(["?" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] += dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    max_scores = [spc[0] * spc[1] + spc[2] for spc in spc_list]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + max_scores[q_idx] < G:
                score += max_scores[q_idx]
                q_num += spc_list[q_idx][1]
            else:
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
            if score >= G or q_num > min_q:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import itertools
import sys
input = sys.stdin.readline

def main():
    D, G = map(int, input().split())
    spc_list = [[(i+1) * 100] + [int(v) for v in input().split()] for i in range(D)]
    max_scores = [spc[0] * spc[1] + spc[2] for spc in spc_list]
    min_q = float("inf")
    for q_list in itertools.permutations(list(range(D))):
        score = 0
        q_num = 0
        for q_idx in q_list:
            if score + max_scores[q_idx] < G:
                score += max_scores[q_idx]
                q_num += spc_list[q_idx][1]
            else:
                q_num += min(math.ceil((G-score) / spc_list[q_idx][0]), spc_list[q_idx][1])
                score = G
                """
                for _ in range(spc_list[q_idx][1]):
                    score += spc_list[q_idx][0]
                    q_num += 1
                    if score >= G:
                        break
                score += spc_list[q_idx][2]
"""
            if score >= G:
                break
        if q_num < min_q:
            min_q = q_num
    print(min_q)


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

p = lambda  x: x #print(x)

PO = "POSSIBLE"
IM = "IMPOSSIBLE"
ans = ""

# def fnc(a, ans):
# 	for i in range(N-1):
# 		if ans != "": break
# 		x = a[N-1-i]
# 		for j in range(N-1):
# 			y = a[j]
# 			if x-y == K:
# 				ans = PO
# 				break
# 			elif x-y < 0:
# 				break
# 			else:
# 				if (x-y) not in a:
# 					a.insert(0,x-y)
# 					print(a)
# 	else:
# 		ans = IM
	

N, K = map(int, input().split())		# 5 7
a = [int(i) for i in input().split()]	# 1 2 3 4 5 ...
a.sort()
p(a)

if max(a)<K:
	ans = IM

if K in a:
	ans = PO

if ans == "":
	for i in range(N-2):
		x = a[i]
		p(x)
		for j in range(i+1, N-1):
			y = a[j]
			p(y)
			b = y%x
			p(b)
			if b!=0 and K%b == 0:
				ans = PO
				p("A")
				break

		if ans != "": break
	else:
		ans = IM
		p("B")


print(ans)


### FIXED CODE ###

import sys
from fractions import gcd

PO = "POSSIBLE"
IM = "IMPOSSIBLE"
ans = ""


N, K = map(int, input().split())		# 5 7
a = sorted(list(map(int, input().split())))	# 1 2 3 4 5 ...

if max(a)<K:
	print(IM)
	sys.exit()

if K in a:
	print(PO)
	sys.exit()

g=a[0]
for i in range(1,N):
	g = gcd(g,a[i])

if K%g==0:
	ans=PO
else:
	ans=IM


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

S = input()
count = 0
for j in range(3, len(S)+1):
    for i in range(j):
        s = int(S[i:j])
        if s % 2019 == 0:
            count += 1
print(count)


### FIXED CODE ###

S = input()
count = 0
exist = [0]*2019
flg = False
N = len(S)
sum = 0
for i, s in enumerate(reversed(S)):
    sum += (int(s) * pow(10, i, 2019)) % 2019
    exist[sum % 2019] += 1
for e in exist:
    if e > 1:
        count += e*(e-1)//2
count += exist[0]
print(count)
### BUGGY CODE ###

class BIT:
    def __init__(self, n):
        self.node = [ 0 for _ in range(n+1) ]

    def add(self, idx, w):
        i = idx
        while i < len(self.node) - 1:
            self.node[i] += w
            i |= (i + 1)

    def sum_(self, idx):
        ret, i = 0, idx-1
        while i >= 0:
            ret += self.node[i]
            i = (i & (i + 1)) - 1
        return ret

    def sum(self, l, r):
        return self.sum_(r) - self.sum_(l)


n = int(input())
s = list(input())
q = int(input())

tree = [ BIT(n) for _ in range(26) ]
for i in range(n):
    tree_id = ord(s[i]) - ord("a")
    tree[tree_id].add(i, 1)

for _ in range(q):
    query = input().split()
    com = int(query[0])
    if com == 1:
        idx, new_char = int(query[1]), query[2]
        idx -= 1
        old_char = s[idx]
        new_id = ord(new_char) - ord("a")
        old_id = ord(old_char) - ord("a")

        tree[old_id].add(idx, -1)
        tree[new_id].add(idx, 1)
        s[idx] = new_char

    if com == 2:
        l, r = int(query[1]), int(query[2])
        ret = 0
        for c in range(26):
            if tree[c].sum(l-1, r) > 0:
                ret += 1
        print(ret)

### FIXED CODE ###

class BIT:
    def __init__(self, n):
        self.node = [ 0 for _ in range(n+1) ]

    def add(self, idx, w):
        i = idx
        while i < len(self.node) - 1:
            self.node[i] += w
            i |= (i + 1)

    def sum_(self, idx):
        ret, i = 0, idx-1
        while i >= 0:
            ret += self.node[i]
            i = (i & (i + 1)) - 1
        return ret

    def sum(self, l, r):
        return self.sum_(r) - self.sum_(l)


n = int(input())
s = list(input())
q = int(input())

tree = [ BIT(n) for _ in range(26) ]
for i in range(n):
    tree_id = ord(s[i]) - ord("a")
    tree[tree_id].add(i, 1)

for _ in range(q):
    query = input().split()
    com = int(query[0])
    if com == 1:
        idx, new_char = int(query[1]), query[2]
        idx -= 1
        old_char = s[idx]
        new_id = ord(new_char) - ord("a")
        old_id = ord(old_char) - ord("a")

        tree[old_id].add(idx, -1)
        tree[new_id].add(idx, 1)
        s[idx] = new_char

    if com == 2:
        l, r = int(query[1]), int(query[2])
        ret = 0
        for c in range(26):
            if tree[c].sum(l-1, r) > 0:
                ret += 1
        print(ret)
### BUGGY CODE ###

n=int(input())
s=[int(input()) for i in range(5)]
a=s[0]
b=s[1]
c=s[2]
d=s[3]
e=s[4]
p=[n, 0, 0, 0, 0, 0]
t=0
while p[5] != n:
  #to6
  if p[4] >= e:
    p[4] -= e
    to6 = e
  else:
    to6 = p[4]
    p[4] = 0
  p[5] += to6
  #to5
  if p[3] >= d:
    p[3] -= d
    to5 = d
  else:
    to5 = p[3]
    p[3] = 0
  p[4] += to5
  #to4
  if p[2] >= c:
    p[2] -= c
    to4 = c
  else:
    to4 = p[2]
    p[2] = 0
  p[3] += to4
  #to3
  if p[1] >= b:
    p[1] -= b
    to3 = b
  else:
    to3 = p[1]
    p[1] = 0
  p[2] += to3
  #to2
  if p[0] >= a:
    p[0] -= a
    to2 = a
  else:
    to2 = p[0]
    p[0] = 0
  p[1] += to2
  t+=1
print(t)

### FIXED CODE ###

import math
N = int(input())
t = min([int(input()) for _ in range(5)])
print(math.ceil(N/t)+4)
### BUGGY CODE ###

import math
N,M = (int(T) for T in input().split())
S = input()
T = input()

Length = N*M//math.gcd(N,M)
Flag   = True
SIndex = [Nk*(Length//N) for Nk in range(0,N)]
SList  = list(S)
    
for Mk in range(0,M):
    if Mk*(Length//M) in SIndex:
        MInd = SIndex.index(Mk*(Length//M))
        if SList[MInd]!=T[Mk]:
            Flag = False
            break
        
if Flag:
    print(Length)
else:
    print(-1)

### FIXED CODE ###

import math
N,M = (int(T) for T in input().split())
S = input()
T = input()
Length = N*M//math.gcd(N,M)
Flag   = True
SIndex = [Nk*(Length//N) for Nk in range(0,N)]
SList  = list(S)
    
for Mk in range(0,M):
    if Mk%(Length//N)==0:
        MInd = SIndex.index(Mk*(Length//M))
        if SList[MInd]!=T[Mk]:
            Flag = False
            break
        
if Flag:
    print(Length)
else:
    print(-1)
### BUGGY CODE ###

N,X,Y = map(int,input().split())
X -= 1
Y -= 1
aggre= [0] * (N - 1)

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    dist = min(abs(j - i),abs(X - i) + abs(Y - j) + 1,abs(Y - i) + abs(X - j) + 1)
    #if dist >= N // 2:
      #print("dist i j",dist,i,j)
    aggre[dist - 1] += 1
    
ans = [i // 2 for i in aggre]
for a in ans:
  print(a)

### FIXED CODE ###

N,X,Y = map(int,input().split())
X -= 1
Y -= 1
aggre= [0] * (N - 1)

for i in range(N):
  for j in range(N):
    if i == j:
      continue
    dist = min(abs(j - i),abs(X - i) + abs(Y - j) + 1,abs(Y - i) + abs(X - j) + 1)
    #if dist >= N // 2:
      #print("dist i j",dist,i,j)
    aggre[dist - 1] += 1
    
#ans = [i // 2 for i in aggre]
for a in aggre:
  print(a // 2)
### BUGGY CODE ###

import queue

def push(n, dist, dist_list):
	if dist_list[n] > dist:
		dist_list[n] = dist
		q.put(n)



q = queue.Queue()
n, x, y = [int(i) for i in input().split()]
result = [0] * (n-1)

for p in range(n):
	dist_list = [111111111111] * n
	dist = 0
	q.put(p)
	dist_list[p] = dist 
	while not q.empty():
		p = q.get()
		dist = dist_list[p]
		if p+1 < n: push(p+1, dist+1, dist_list)
		if p-1 >= 0: push(p-1, dist+1, dist_list)
		if p == (x-1): push(y-1, dist+1, dist_list)
		if p == (y-1): push(x-1, dist+1, dist_list)
	
	for i in dist_list:
		if i != 0:
			result[i-1] += 1

for ans in result:
	print(ans//2)
		




### FIXED CODE ###

n, x, y = [int(i) for i in input().split()]
# 0 index is 1 distance
result = [0] * (n-1)

for i in range(n-1):
	for j in range(i+1, n):
		dist = min(j-i, abs(x-1-i) + 1 + abs(j-y+1))
		result[dist-1] += 1

for ans in result:
	print(ans)


# TLE

# import queue
	
# q = queue.Queue()
# n, x, y = [int(i) for i in input().split()]
# result = [0] * (n-1)

# for p in range(n):
# 	dist_list = [111111] * n
# 	dist = 0
# 	q.put(p)
# 	dist_list[p] = dist 
# 	while not q.empty():
# 		p = q.get()
# 		dist = dist_list[p]
# 		if p+1 < n: 
# 			if dist_list[p+1] > dist:
# 				dist_list[p+1] = dist
# 				q.put(p+1)
# 		if p-1 < n: 
# 			if dist_list[p-1] > dist:
# 				dist_list[p-1] = dist
# 				q.put(p-1)
# 		if p == (x-1): 
# 			if dist_list[y-1] > dist:
# 				dist_list[y-1] = dist
# 				q.put(y-1)
# 		if p == (y-1): 
# 			if dist_list[x-1] > dist:
# 				dist_list[x-1] = dist
# 				q.put(x-1)

# 	for i in dist_list:
# 		if i != 0:
# 			result[i-1] += 1

# for ans in result:
# 	print(ans//2)
### BUGGY CODE ###

import numpy as np

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

max_sum = 0
for i in range(N-K+1):
    max_sum = max(max_sum, np.sum(P[i:i+K]))
    
print((max_sum + K) / 2)

### FIXED CODE ###

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

E = [0 for i in range(N+1)]
for i in range(N):
    E[i+1] = E[i] + (P[i] + 1) / 2
    
ans = 0
for i in range(N-K+1):
    ans = max(ans, E[i+K] - E[i])

print(ans)