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

import math
from functools import reduce


def gcd(*nums):
  return reduce(math.gcd, nums)


input_num = int(input()) + 1
result = 0
for a in range(1, input_num):
  for b in range(1, input_num):
    for c in range(1, input_num):
      if a == b == c:
        result += a
      else:
        result += gcd(a, b, c)
print(result)


### FIXED CODE ###

import math
from functools import reduce

def gcd(*nums):
  return reduce(math.gcd, nums)


input_num = int(input()) + 1
result = 0
for a in range(1, input_num):
  for b in range(1, input_num):
    for c in range(1, input_num):
        result += gcd(a, b, c)

print(result)
### BUGGY CODE ###

n = int( input() )
s = list( input() )
r = []
g = []
b = []

for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
    elif s[i] == "B":
        b.append(i) 

cnt = 0
for i in r:
    for j in g:
        for k in b:
            if (i+j)/2==k or (j+k)/2==i or (k+i)/2==j:
                cnt += 1

print( len(r) * len(g) * len(b) - cnt )

### FIXED CODE ###

n = int( input() )
s = list( input() )
r = []
g = []
b = []

for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
    elif s[i] == "B":
        b.append(i) 

cnt = 0
for i in range(n - 2):
    for k in range(i + 2, n):
        if ( i + k ) % 2 != 0:
            continue
        j = ( i + k ) // 2
        if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
            cnt += 1

print( len(r) * len(g) * len(b) - cnt )
### BUGGY CODE ###

N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

answer = -float('inf')
for start_p in range(1, N+1):

    cycle_total_score = 0
    cycle_in_score = -float('inf')
    cycle_count = 0
    next_p = P[start_p]
    while True:
        cycle_total_score += C[next_p]
        cycle_in_score = max(cycle_in_score, cycle_total_score)
        cycle_count += 1

        if next_p == start_p:
            # print('start_p:', start_p, ' cycle_total_score:', cycle_total_score, 'cycle_in_score:', cycle_in_score, 'cycle_count:', cycle_count)
            break
        next_p = P[next_p]

    max_score = 0
    if K == cycle_count:
        max_score = cycle_in_score
    else:
        #あふれたK % cycle_count回数分だけスコアを足すためにmaxを探さす
        add_max_count = K % cycle_count
        add_total_score = 0
        add_score = -float('inf')
        add_count = 0
        add_next_p = P[start_p]
        while True:
            add_total_score += C[add_next_p]
            add_score = max(add_score, add_total_score)
            add_count += 1

            if add_count == add_max_count:
                break
            add_next_p = P[add_next_p]

        if K < cycle_count:
            #最大の試行回数がcycle_countよりも小さい場合K % cycle_countまでで一番良いところでbeak
            max_score = add_total_score
        else:
            if cycle_total_score >= 0:
                #1サイクルでプラスの場合はできるだけサイクルを回してK % cycle_countまでで一番良いところでbeak
                max_score = (K // cycle_count) * cycle_total_score + add_total_score
            else:
                #1サイクルでマイナスの場合はサイクルを回さないで、K % cycle_countまでで一番良いところでbreak
                max_score = add_total_score
    # print('max_score', max_score)
    answer = max(answer, max_score)

print(answer)


### FIXED CODE ###

n,k=map(int,input().split())
#0-indexed
p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))
#1回以上K回以下
ansF=-1000000000000000000
for i in range(n):
    #すでに辿ったもの
    check=[False]*n
    #辿った順番
    turns=[]
    #今
    now=i
    while check[now]==False:
        check[now]=True
        turns.append(now)
        now=p[now]
    #答え(今の)
    ans=0
    #kのうち何回分
    #更新を毎回行う
    spare=turns.index(now)
    if spare>=k:
        for j in range(k):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    for j in range(spare):
        ans+=c[turns[j]]
        ansF=max(ans,ansF)
    turns=turns[spare:]
    spare=k-spare
    #サイクルの長さ
    l=len(turns)
    #サイクルの和(あまりも)
    #サイクルどこで止めるか
    x=0
    for j in range(l):
        x+=c[turns[j]]
    #そもそもサイクル回らない場合
    if spare<=l:
        for j in range(spare):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    #サイクル回した方が良い場合
    #最後のサイクルは回さない方が良いパターンも
    if x>=0:
        ans+=(x*(spare//l-1))
        ansF=max(ans,ansF)
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        for j in range(spare%l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
    #サイクル回さない方がいい場合
    else:
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
print(ansF)
### BUGGY CODE ###

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

ans = 0

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

mod = 10**9 + 7
print(ans%mod)

### FIXED CODE ###

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

ans = 0
res = [0] * N
res[0] = A[0]
for i in range(len(A)-1):
    res[i+1] = res[i] + A[i+1]

sum_A = sum(A)

for i in range(N-1):
  ans += A[i]*(sum_A-res[i])
  
mod = 10**9 + 7
print(ans%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
 
a = list(map(int, input().split()))
 
res = [0]
tmp = 0
 
tf = [-1 for i in range(n)]
tf[0] = 0
 
for i in range(n):
    tmp = a[tmp] - 1
    if tf[tmp] != -1:
        start = tmp
        break
    else:
        res = res + [tmp]
        tf[tmp] = i+1
 
lenret = i+1
stridx = tf[start]
 
cycle = lenret - stridx
 
if stridx >= k:
    print(res[k]+1)
    exit()
else:
    k = k - stridx
 
    tmp = k % cycle
 
    print(res[stridx+tmp]+1)

### FIXED CODE ###

n, k = map(int, input().split())

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

res = [0]
tmp = 0

tf = [-1 for i in range(n)]
tf[0] = 0

for i in range(n):
    tmp = a[tmp] - 1
    if tf[tmp] != -1:
        start = tmp
        break
    else:
        res.append(tmp)
        tf[tmp] = i+1

lenret = i+1
stridx = tf[start]

cycle = lenret - stridx

if stridx >= k:
    print(res[k]+1)
    exit()
else:
    k = k - stridx

    tmp = k % cycle

    print(res[stridx+tmp]+1)
### BUGGY CODE ###

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
set_a = set(a)
ans=0
while len(set_a) > k:
    i = -1
    c = Counter(a).most_common()[i]  # (出現回数の最も少ない数字,出現回数)
    num = c[0]
    ans += c[1]
    set_a.remove(num)
    for _ in range(c[1]):
        a.remove(num)  # リストの操作回数...
    i-=1
print(ans)


### FIXED CODE ###

from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
set_a = set(a)
ans = 0
i = -1
c = Counter(a).most_common() # (出現回数の最も少ない数字,出現回数)
while len(set_a) > k:
    set_a.remove(c[i][0])
    ans += c[i][1]
    i-=1
print(ans)
### BUGGY CODE ###

import math
N=int( input())
for r in range (int(math.sqrt(N)),N+1):
  if N%r==0:
    count=1
    for i in range (0,9):
      r=r/10
      if r<1:
        print(count)
        break
      count+=1
    break

### FIXED CODE ###

import math
N=int( input())
for r in range (int(math.sqrt(N)),0,-1):
  if N%r==0:
    count=1
    l=N/r
    for i in range (0,10):
      l=l/10
      if l<1:
        print(count)
        break
      count+=1
    break
### BUGGY CODE ###

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

max_s = 0
for i in range(N):
  if i+K < N and P[i] < P[i+K]:
    i = i + K
    continue
    
  sum_K = sum(P[0+i:K+i])
  if max_s < sum_K:
    max_s = sum_K

print((max_s+K) / 2)

### FIXED CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
s = [0] * 1000000
for i in range(N):
    s[i+1] = s[i] + A[i]

max_s = 0
for i in range(N):
    if max_s < s[i+K] - s[i]:
        max_s = s[i+K] - s[i]


print((max_s+K) / 2)
### BUGGY CODE ###

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

max_l = max(lr, key=lambda x:x[1])[1]

prime =[2]
for i in range(2,max_l+1):
    for j in prime:
        if i % j == 0:
            break
        else:
            if j == prime[-1]:
                prime.append(i)

for i in range(Q):
    count = 0
    for j in range(lr[i][0],lr[i][1]+2,2):
        if (j in prime) and ((j+1)/2 in prime):
            count += 1
    print(count)


### FIXED CODE ###

import math
Q = int(input())
lr = [list(map(int, input().split())) for i in range(Q)]

max_l = max(lr, key=lambda x:x[1])[1]

prime = list(range(2,int(math.ceil(max_l**0.5)+1)))

m = 1
while True:
    b = filter(lambda x: x%prime[m-1] != 0,prime[m:])
    prime = prime[:m]
    prime.extend(b)
    m += 1
    if m > len(prime):
        break

like2017 = {-1:0,1:0}
for i in range(3,max_l+2,2):
    k = 0
    for j in prime:
        if (i%j == 0 or ((i+1)/2)%j == 0) and i != j and (i+1)/2 != j:
            k += 1
            break
    if k == 0:
        like2017[i] = like2017[i-2] + 1
    else:
        like2017[i] = like2017[i-2]


for i in range(Q):
    print(like2017[lr[i][1]]-like2017[lr[i][0]-2])
### BUGGY CODE ###

N, M = map(int, input().split())

dp = [float("inf")] * (2 ** N)

dp[0] = 0

for i in range(M):
    
    a, b = map(int, input().split())
    c = list(map(int, input().split()))

    key = 0

    for j in c:
        key += 2 ** (j-1)

    for j in range(2**N):
        dp[j | key] = min(dp[j | key], dp[j] + a)

if dp[2 ** N - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** N - 1])

### FIXED CODE ###

N, M = map(int, input().split())

dp = [float("inf")] * (2 ** N)

dp[0] = 0

for i in range(M):

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

    key = 0

    for j in c:
        key += 2 ** (j-1)

    for j in range(2**N):
        if dp[j | key] > dp[j] + a:
            dp[j | key] = dp[j] + a

if dp[2 ** N - 1] == float("inf"):
    print(-1)
else:
    print(dp[2 ** N - 1])
### BUGGY CODE ###

N, M = map(int, input().split())
set1 = set([x for x in range(1, N+1)])
for i in range(M):
  L, R = map(int, input().split())
  lr = set([x for x in range(L, R+1)])
  set1 =set1 & lr
print(len(set1))

### FIXED CODE ###

N, M = map(int, input().split())
L, R = map(int, input().split())


for i in range(M-1):
      L1, R1 = map(int, input().split())
      if R1 < L or R < L1:
        print(0)
        exit()
      else:
        if L <= L1 <= R:
          L = L1
          
        elif L <= R1 <= R:
          R = R1
        
          
print(R-L+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from itertools import accumulate

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

MOD = 10**9 + 7

N = d_in()
A_list = ds_in()

def factorial(N):
    val = 1
    for i in range(1, N+1):
        val = (val * i) % MOD
    return val

def recursive_square(n, m, p):
    """ n**p (mod m) """
    if p == 0:
        return 1 % m
    if p % 2 == 0:
        root = recursive_square(n, m, p//2) % m 
        return (root ** 2) % m
    else:
        return ((n % m) * recursive_square(n, m, p-1)) % m


N_factorial = factorial(N)

Coefs = []
for i in range(1, N+1):
    Coefs.append((N_factorial * recursive_square(i, MOD, MOD-2)) % MOD)

Cum_Coefs = list(accumulate(Coefs))

if N == 1:
    print(A_list[0])
else: 
    ans = 0
    for i in range(N):
        ans = (ans + A_list[i] * (Cum_Coefs[i] + Cum_Coefs[N-i-1] - Cum_Coefs[0])) % MOD 
    print(ans)



### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
from itertools import accumulate

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

MOD = 10**9 + 7

N = d_in()
A_list = ds_in()

def factorial(N):
    val = 1
    for i in range(1, N+1):
        val = (val * i) % MOD
    return val

def recursive_square(n, m, p):
    """ n**p (mod m) """
    if p == 0:
        return 1 % m
    if p % 2 == 0:
        root = recursive_square(n, m, p//2) % m 
        return (root ** 2) % m
    else:
        return ((n % m) * recursive_square(n, m, p-1)) % m
        
def factorize(n):
    if n == 1:
        return [(1, 1)]
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n //= b
            e += 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

N_factorial = factorial(N)

Coefs = []
lastval = 0
Inv = dict()
for i in range(1, N+1):
    fac = factorize(i)
    temp = N_factorial
    for f in fac:
        if f[0] not in Inv.keys():
            Inv[f[0]] = recursive_square(f[0], MOD, MOD-2)
        for _ in range(f[1]):
            temp = (temp * Inv[f[0]]) % MOD
    lastval = (lastval + temp) % MOD
    Coefs.append(lastval)

if N == 1:
    print(A_list[0])
else: 
    ans = 0
    for i in range(N):
        ans = (ans + A_list[i] * (Coefs[i] + Coefs[N-i-1] - Coefs[0])) % MOD 
    print(ans)
### BUGGY CODE ###

class DualSegTree():
    def __init__(self,n):
        self.n=n
        self.data=[0]*n*2
    def propagate(self,i):
        if i>=self.n*2:return
        data=self.data
        c,j=0,i
        while j:
            j>>=1
            c+=1
        for j in range(c-1,0,-1):
            j=i>>j
            data[j+j]+=data[j]
            data[j-~j]+=data[j]
            data[j]=0
    def update(self,l,r,x):
        data=self.data
        l+=self.n
        r+=self.n
        self.propagate(l)
        self.propagate(r)
        while l<r:
            if l&1:
                data[l]+=x
                l+=1
            if r&1:
                r-=1
                data[r]+=x
            l>>=1
            r>>=1
    def get(self,i):
        i+=self.n
        self.propagate(i)
        return self.data[i]
def main():
    n,k,*a=map(int,open(0).read().split())
    seg=DualSegTree(n)
    seg.data[n:]=a
    for _ in range(k):
        d=DualSegTree(n)
        get,update=seg.get,d.update
        m=10**18
        for i in range(n):
            t=get(i)
            if t<m:m=t
            update(max(0,i-t),min(i-~t,n),1)
        seg=d
        if m>n:break
    print(' '.join(str(seg.get(i))for i in range(n)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

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

n_total = 0
S_ik, S_jk = [], []
for i in range(0,N-2):
  tmp = []
  for k in range(i+2,N):
    if S[i] != S[k]:
      tmp.append(k)
  S_ik.append(tmp)
for j in range(1,N-1):
  tmp = []
  for k in range(j+1,N):
    if S[j] != S[k]:
      tmp.append(k)
  S_jk.append(tmp)
for i in range(0,N-2):
  for j in range(i+1,N-1):
    if S[i] != S[j]:
      group = list(set(S_ik[i])&set(S_jk[j-1]))
      for k in range(len(group)):
        if (j-i) != (group[k]-j):
          n_total+=1
print(n_total)

"""
for i in range(0,N-2):
  for j in range(i+1,N-1):
    if S[i] != S[j]:
      for k in range(j+1,N):
        if S[i] != S[k] and S[j] != S[k] and (j-i) != (k-j): 
          n_total+=1
print(n_total)
"""

### FIXED CODE ###

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

n_R, n_G, n_B, n_total = 0, 0, 0, 0
for i in range(N):
  if S[i] == 'R':
    n_R+=1
  elif S[i] == 'G':
    n_G+=1
  else:
    n_B+=1
n_total += (n_R*n_G*n_B)
for j in range(1,N-1):
  i = j-1
  k = j+1
  while 1:
    if 0 <= i and k < N:
      if S[i] != S[j] and S[j] != S[k] and S[i] != S[k]:
        #print(i,j,k, S[i], S[j], S[k])
        n_total-=1
    else:
      break
    i -= 1
    k += 1
print(n_total)
### BUGGY CODE ###

# DPの計算量…DPテーブルのノードの数＋エッジの数
# https://atcoder.jp/contests/dp/tasks/dp_b


def chmin(a, b):
    '''a>bならbを代入して返すメソッド'''
    if a > b:
        a = b
        return a
    else:
        return a


def main():
    '''もらうDPとして実装'''
    N, K = list(map(int, input().split()))
    H = list(map(int, input().split()))
    # 最小なものにコストを書き換えたいので初期値は大きく取る
    dp = [1000000000] * N

    # 最初はコスト０
    dp[0] = 0
    for i in range(1, N):
        dp[i] = chmin(dp[i], dp[i - 1] + abs(H[i] - H[i - 1]))
        for j in range(2, min(i+1, K + 1)):
            dp[i] = chmin(dp[i], dp[i - j] + abs(H[i] - H[i - j]))
    print(dp[i])


main()


### FIXED CODE ###

def test():
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    dp = [float('inf')]*N
    dp[0] = 0
 
    for i in range(1, N):
        dp[i] = min(dp[j] + abs(H[i] - H[j]) for j in range(max(i-K, 0), i))
 
    print(dp[-1])
 
if __name__ == '__main__':
    test()
### BUGGY CODE ###

N=int(input())
S=str(input())
result = float('inf')
for i in range(N):
  S_1 = S[:i].count('W')
  S_2 = S[i+1:].count('E')
  result = min(result,S_1+S_2)
print(result)

### FIXED CODE ###

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

E=[0]*N
W=[0]*N
c=0
for i in range(N):
  W[i] =c
  if S[i]=='W':
    c +=1
c=0
for j in range(N):
  E[-1-j]=c
  if S[-1-j]=='E':
    c +=1
E=[E[0]]+E+[0]
W=[0]+W+[W[-1]]
answer=float('inf')
for i in range(N+2):
  answer=min(answer,E[i]+W[i])
print(answer)
### BUGGY CODE ###


def kakaka():
    a = list(map(int, input().split()))
    b = map(int, input().split())
    c = int(input())

def start_process():
    return
def main():
    all_num, inst_num = map(int, input().split())
    data = list(input())

    data_la = []
    ans_0, ans_1 = 0, 0
    for i in range(all_num):
        if data[i] == '1':
            ans_1 += 1
            if ans_0 > 0:
                data_la.append(ans_0)
                ans_0 = 0
        else:
            ans_0 += 1
            if ans_1 > 0:
                data_la.append(ans_1)
                ans_1 = 0
    if ans_1 > 0:
        data_la.append(ans_1)
    elif ans_0 > 0:
        data_la.append(ans_0)

    ans_data = 0
    if data[0] == '1':
        for i in range(len(data_la))[::2]:
            fin = min(len(data_la), i + inst_num * 2 + 1)
            now_count = sum(data_la[i : fin])
            if ans_data < now_count:
                ans_data = now_count
            if fin >= len(data_la):
                break

    if data[0] == '0':
        fin = min(len(data_la), inst_num * 2)
        ans_data = sum(data_la[0: fin])
        for i in range(1, len(data_la))[::2]:
            fin = min(len(data_la), i + inst_num * 2 + 1)
            now_count = sum(data_la[i: fin])
            if ans_data < now_count:
                ans_data = now_count
            if fin >= len(data_la):
                break

    print(ans_data)






if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    all_num, inst_num = map(int, input().split())
    data = list(input())

    data_la = []
    ans_0, ans_1 = 0, 0
    for i in range(all_num):
        if data[i] == '1':
            ans_1 += 1
            if ans_0 > 0:
                data_la.append(ans_0)
                ans_0 = 0
        else:
            ans_0 += 1
            if ans_1 > 0:
                data_la.append(ans_1)
                ans_1 = 0
    if ans_1 > 0:
        data_la.append(ans_1)
    elif ans_0 > 0:
        data_la.append(ans_0)

    ans = 0
    ans_data = 0
    count_0 = 0

    if data[0] == '0':
        data_la.insert(0, 0)

    # print(data_la)

    if len(data_la) <= 2:
        ans_data = sum(data_la)
    else:
        pre_data1_ind, pre_data2_ind = 0, 1
        pre_data1, pre_data2 = data_la[pre_data1_ind], data_la[pre_data2_ind]

        for i in range(len(data_la)):
            if i % 2 == 1:
                count_0 += 1

            if count_0 == inst_num + 1:
                ans = ans - pre_data1 - pre_data2
                pre_data1_ind += 2
                pre_data2_ind += 2
                if pre_data1_ind >= len(data_la):
                    pre_data1 = 0
                else:
                    pre_data1 = data_la[pre_data1_ind]
                if pre_data2_ind >= len(data_la):
                    pre_data2 = 0
                else:
                    pre_data2 = data_la[pre_data2_ind]
                count_0 -= 1

            ans += data_la[i]
            if ans_data < ans:
                ans_data = ans

    print(ans_data)


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

x,k,d = map(int, input().split())
y = x
for i in range(k):
  if x > 0:
    x -= d
    y = min(abs(y),abs(x))
  elif x < 0:
    x += d
    y = min(abs(y),abs(x))
  else:
    if (k-i)%2 == 1:
      y = d
    else:
      y = 0
    break
print(y)

### FIXED CODE ###

x,k,d = map(int, input().split())

x = abs(x)
if k <= x//d:
  y = x-k*d
else:
  if (k-x//d)%2 == 0:
    y = x%d
  else:
    y = min(abs(x%d-d),abs(x%d+d))
print(y)
### BUGGY CODE ###

N=int(input())
now=0
T=list(map(int,input().split()))
for i in range(1,N):
    T[i]+=T[i-1]
T=[-1*float('inf'),0]+T+[float('inf')]
V=list(map(int,input().split()))
V=[0]+V+[0]
vt=[float('inf')]*(2*T[-2]+1)
for t in range(len(vt)):
    now=t/2
    for k in range(N+2):
        if now<T[k]:
            vt[t]=min(vt[t],V[k]+T[k]-now)
        elif T[k]<=now<=T[k+1]:
            vt[t]=min(vt[t],V[k])
        elif T[k+1]<now:
            vt[t]=min(vt[t],V[k]+now-T[k+1])
ans=0
for i in range(len(vt)-1):
    ans+=0.25*(vt[i]+vt[i+1])
print(ans)

### FIXED CODE ###

N=int(input())
now=0
T=list(map(int,input().split()))
for i in range(1,N):
    T[i]+=T[i-1]
T=[-1*float('inf'),0]+T+[float('inf')]
V=list(map(int,input().split()))
V=[0]+V+[0]
vt=[float('inf')]*(T[-2]+1)
for t in range(len(vt)):
    now=t
    for k in range(N+2):
        if now<T[k]:
            vt[t]=min(vt[t],V[k]+T[k]-now)
        elif T[k]<=now<=T[k+1]:
            vt[t]=min(vt[t],V[k])
        elif T[k+1]<now:
            vt[t]=min(vt[t],V[k]+now-T[k+1])
ans=0
for i in range(len(vt)-1):
    if abs(vt[i+1]-vt[i])==1:
        ans+=0.5*(vt[i]+vt[i+1])
    elif vt[i+1]==vt[i]:
        for k in range(N+2):
            if T[k]<=i and i+1<=T[k+1]:
                vv=V[k]
                break
        if vv>vt[i]:
            ans+=0.5*(vt[i]*2+0.5)
        else:
            ans+=vt[i]
print(ans)
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None in ANS[i:i+L] :
            while True:
                if ANS[i] :
                    i += 1
                    continue
                else : 
                    ANS[i] = min(Whole[i+1-L:i+1])
                    i += 1
                    break
        else :
            i += L
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.991
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])