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

import sys
from itertools import accumulate
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n,k = map(int,sys.stdin.readline().rstrip().split())
    a = LI()
    for _ in range(k):
        table = [0]*(n+1)
        for i,x in enumerate(a):
            table[max(0,i-x)] += 1
            table[min(n-1,i+x)+1] -=1
        a = list(accumulate(table))[:-1]
    print(*a)
    return

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
from itertools import accumulate

def solve(n,k,a):
    for _ in range(k):
        if a==[n]*n:    return a
        t = [0]*(n+1)
        for i,x in enumerate(a):
            t[max(0,i-x)] += 1
            t[min(n,i+x+1)] -=1
        a = list(accumulate(t))[:-1]
    return a

n,k = map(int,sys.stdin.readline().rstrip().split())
a = list(map(int,sys.stdin.readline().rstrip().split()))

print(*solve(n,k,a))
### BUGGY CODE ###

import math
N ,a,b= list(map(int,input().split(' ')))


M = 10**9+7

def pow(x,n):
    if n==0:
        return 1
    res = pow((x*x)%M,n//2)
    if (n%2)==1:
        res = (res*x)%M
    return res


def power(x,n):
    res = 1
    if(n>0):
        res = power(x,n//2)
        if (n%2)==0:
            res = (res*res)%M
        else:
            res = (((res*res)%M)*x)%M
    return res

def comb(n,a):
    ans = 1
    for i in range(a):
        ans = (ans*(n-i))%M
        ans = (ans*power(i+1,M-2))%M 
    return ans

#print(pow(10,2))
#print(power(5,8))

print((power(2,N)-1-comb(N,a)-comb(N,b))%M)

### FIXED CODE ###

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


M = 10**9+7

def pow(x,n):
    if n==0:
        return 1
    res = pow((x*x)%M,n//2)
    if (n%2)==1:
        res = (res*x)%M
    return res


def power(x,n):
    res = 1
    if(n>0):
        res = power(x,n//2)
        if (n%2)==0:
            res = (res*res)%M
        else:
            res = (((res*res)%M)*x)%M
    return res

def comb(n,a):
    ans = 1
    for i in range(a):
        ans = (ans*(n-i))%M
        ans = (ans*power(i+1,M-2))%M 
    return ans

#print(pow(10,2))
#print(power(5,8))

print((power(2,N)-1-comb(N,a)-comb(N,b))%M)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
m = max(A)

for i in range(n):
    if i == A.index(max(A)):
        ans = A[:]
        ans.pop(i)
        print(max(ans))
    else:
        print(m)


### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
B = A[:]
B.sort()

a_max = B[len(B)-1]
a_next = B[len(B)-2]

for i in range(n):
    if A[i] != a_max:
        print(a_max)
    else:
        print(a_next)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
########   modあり modは素数  ###############
def cmb(n, r, mod):
    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 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

#print(s,f)
mod=10**9+7
for i in range(1,n+1):
    """sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)"""
    if i==1:
        sousuu=n+1
        tyouhuku=1
    else:
        sousuu*=(n+2-i)
        sousuu//=i
        tyouhuku*=(s+n-f+1-i+1)
        tyouhuku//=(i-1)
    #print(sousuu,tyouhuku)
    print((sousuu-tyouhuku)%mod)
print(1)


### FIXED CODE ###

import sys
input = sys.stdin.readline
########   modあり modは素数  ###############
def cmb(n, r, mod):
    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 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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


n=int(input())
A=list(map(int,input().split()))
v=[-1]*n
for i,a in enumerate(A):
    #print(i,a)
    if v[a-1]!=-1:
        s=v[a-1]
        f=i
    if v[a-1]==-1:
        v[a-1]=i

#print(s,f)
mod=10**9+7
for i in range(1,n+1):
    sousuu=cmb(n+1,i,mod)
    tyouhuku=cmb(s+n-f,i-1,mod)
    """if i==1:
        sousuu=n+1
        tyouhuku=1
    else:
        sousuu*=(n+2-i)
        sousuu//=i
        tyouhuku*=(s+n-f+1-i+1)
        tyouhuku//=(i-1)"""
    #print(sousuu,tyouhuku)
    print((sousuu-tyouhuku)%mod)
print(1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

a, b, n = map(int, input().replace("\n","").split())

ans = 0

#bがnよりも大きい時
if b > n:
    ans = int(a*n/b)
    print(ans)
    exit()

#b==nのときは、終了間際の2個だけ比較する
elif b == n:
    for i in range(n-1,n+1):
        tmpans = int(a*i/b) - (a*int(i/b))
        if tmpans >= ans:
            ans = tmpans
    print(ans)
    exit()

#これ以外の時は、nはb値ごとにスキップする。
else:
    for i in range(1,n+1,b):
        tmpans = int(a*(i-2)/b) - (a*int((i-2)/b))
        if tmpans >= ans:
            ans = tmpans

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

a, b, n = map(int, input().replace("\n","").split())

ans = 0

#bがnよりも大きい時
if b > n:
    ans = int(a*n/b)
    print(ans)
    exit()

#b==nのときは、終了間際の2個だけ比較する
elif b == n:
    for i in range(n-1,n+1):
        tmpans = int(a*i/b) - (a*int(i/b))
        if tmpans >= ans:
            ans = tmpans
    print(ans)
    exit()

#これ以外の時は、nはb値ごとにスキップする。
else:
    for i in range(int(n/b),n+1,b):
        tmpans = int(a*(i-2)/b) - (a*int((i-2)/b))
        if tmpans >= ans:
            ans = tmpans

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

p=int(input())
n = 10**5
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
lists=[]
for i in prime:
    lists.append(i)  
lists=sorted(lists) 
for i in range(p):
    count=0
    a,b=map(int,input().split())
    for j in range(a,b+1):
        if j in prime and (j+1)%2==0 and (j+1)//2 in prime:
            count+=1
    print(count)

### FIXED CODE ###

q=int(input())
n =10**3
prime = {i for i in range(2,n)}
for i in range(2,n):
    if i in prime:
        for j in range(i*2,n,i):
            if j in prime:
                prime.remove(j)
lists=[]
for i in prime:
    lists.append(i)  
lists=sorted(lists) 

checklist=[0]*(10**5+1)
checklist[0]=0
checklist[1]=0
count=0
for i in range(2,10**5+1):
    if i%2==0:
        checklist[i]=checklist[i-1]
    elif i%2!=0:
        if (all(i%j!=0 for j in lists) or i in lists) and (all(((i+1)//2)%j!=0 for j in lists) or (i+1)//2 in lists) :
            count+=1
            checklist[i]=checklist[i-1]+1
        else:
            checklist[i]=checklist[i-1]

listss=[0]*q
for i in range(q):
    a,b=map(int,input().split())
    c=checklist[b]-checklist[a-1]
    listss[i]=c
for i in listss:
    print(i)
### BUGGY CODE ###

import math

def find_divisor(num):
    q = math.floor(math.sqrt(num))

    while num % q is not 0:
        q -= 1

    return q

S = int(input())

q = find_divisor(S)

x1, y1 = [0, 0]
x2, y2 = [q, 0]
x3, y3 = [0, S//q]

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))


### FIXED CODE ###

S = int(input())

x1, y1 = [0, 0]
x2 = 10 ** 9
y2 = 1

if S % 10 ** 9 == 0:
    y3 = S // 10 ** 9
    x3 = 0
else:
    y3 = (S // 10 ** 9) + 1
    x3 = 10 ** 9 - (S % 10 ** 9)

print("{} {} {} {} {} {}".format(x1, y1, x2, y2, x3, y3))
### BUGGY CODE ###

from collections import deque
A = deque(input())
while A != deque() and A != deque([0]):
    if list(A)[:7] == list("dreamer") and list(A)[5:10] != list("erase"):
        for _ in range(7):
            A.popleft()
    elif list(A)[:5] == list("dream"):
        for _ in range(5):
            A.popleft()
    elif list(A)[:6] == list("eraser"):
        for _ in range(6):
            A.popleft()
    elif list(A)[:5] == list("erase"):
        for _ in range(5):
            A.popleft()
    else:
        A = deque([0])
if A == deque():
    print("YES")
else:
    print("NO")


### FIXED CODE ###

s = input().replace("eraser", "").replace("erase", "")
s = s.replace("dreamer", "").replace("dream", "")
if s:
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

d = [[0]*(W+2)] + [[0]+[INF]*W+[0] for _ in range(H)] + [[0]*(W+2)]# '#'からの距離

for i in range(1,H+1):
  for j,c in enumerate(input(),1):
    if c == '#':
      d[i][j] = 0
      q.append((0,i,j))

ans = 0
qq = []
while q:
  for dv,x,y in q:
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
      xx = x+dx
      yy = y+dy
      if d[xx][yy] == INF:
        d[xx][yy] = dv+1
        ans = dv+1
        qq.append((dv+1,xx,yy))
  q = qq
  qq = []
  
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

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

for i in range(k):
	if a > 0:
		a -= 1
	elif b > 0:
		b -= 1

print(a, b)

### FIXED CODE ###

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

if a > k:
	a = a - k
else:
	k = k - a
	a = 0
	if b > k:
		b = b - k
	else:
		b = 0	

print(a, b)
### BUGGY CODE ###

import sys

iter_num = 5 * (10**5) + 10
sys.setrecursionlimit(iter_num)

s = input()
n = len(s) + 1

a = [0 for _ in range(n)]
next_num=0

def solve(num):
	global next_num
	if num == 0:
		if s[0] == '<':
			a[num] = 0
			next_num = 1
			return 0
		else:
			next_num = 1
			a[num] = solve(num+1) + 1
	if num == n-1:
		if s[n-2] == '>':
			next_num = -1
			a[num] = 0
			return 0
		else:
			a[num] = solve(num-1) + 1
			next_num = -1
			return a[num]

	if s[num-1] == '>' and s[num] == '<':
		next_num = num+1
		a[num] = 0
		return 0
	elif s[num-1] == '>' and s[num] == '>':
		next_num = num+1
		a[num] = solve(num+1) + 1
		return a[num]
	elif s[num-1] == '<' and s[num] == '>':
		next_num = num+1
		a[num] = max(solve(num-1),solve(num+1)) + 1
		return a[num]
	else:
		a[num] = solve(num-1) + 1
		next_num = num+1
		return a[num]

while next_num != -1:
	solve(next_num)

#print(a)
print(sum(a))


### FIXED CODE ###

import sys

iter_num = 5 * (10**5) + 10
sys.setrecursionlimit(iter_num)

s = input()
n = len(s) + 1

a = [0 for _ in range(n)]
next_num=0

def solve(num):
	global next_num
	if num == 0:
		if s[0] == '<':
			a[num] = 0
			next_num = 1
			return 0
		else:
			next_num = 1
			a[num] = solve(num+1) + 1
	if num == n-1:
		if s[n-2] == '>':
			next_num = -1
			a[num] = 0
			return 0
		else:
			a[num] = solve(num-1) + 1
			next_num = -1
			return a[num]

	if s[num-1] == '>' and s[num] == '<':
		next_num = num+1
		a[num] = 0
		return 0
	elif s[num-1] == '>' and s[num] == '>':
		a[num] = solve(num+1) + 1
		return a[num]
	elif s[num-1] == '<' and s[num] == '>':
		next_num = num+1
		a[num] = max(solve(num-1),solve(num+1)) + 1
		return a[num]
	else:
		#a[num] = solve(num-1) + 1
		a[num] = a[num-1] + 1
		next_num = num+1
		return a[num]

while next_num != -1:
	solve(next_num)

#print(a)
print(sum(a))
### BUGGY CODE ###

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

import numpy as np
a = np.array(a)

for i in range(n):
    a_new = np.delete(a, i)
    a_new = np.insert(a_new, 0, 0)
    a_new = np.append(a_new, 0)
    print(np.sum(np.abs(np.diff(a_new))))


### FIXED CODE ###

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

a.insert(0, 0)
a.append(0)

total_tmp = 0
for i in range(1, n+2):
    total_tmp += abs(a[i] - a[i-1])

for i in range(1, n+1):
    # delete the i-th spot
    total = total_tmp - abs(a[i] - a[i-1]) - abs(a[i+1] - a[i]) + abs(a[i+1] - a[i-1])
    print(total)
### BUGGY CODE ###

import sys

sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))

a = [x for x in a if x % 2 == 0]

cnt = 0
while a:
    a.sort(reverse=True)
    if a[0] % 2 == 0:
        a[0] //= 2
        if a[0] % 2 != 0:
            del a[0]
        cnt += 1
    else:
        break

print(cnt)

### FIXED CODE ###

import math
import sys

sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))

a = [x for x in a if x % 2 == 0]

cnt = 0
for x in a:
    while x % 2 == 0:
        x //= 2
        cnt += 1

print(cnt)
### BUGGY CODE ###

MOD = 10 ** 9 + 7


def main(S, T):
  sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

  for i, s in enumerate(S):
    for j, t in enumerate(T):
      v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
      sdp[i + 1][j + 1] = v % MOD

  return (sdp[-1][-1] + 1)


if __name__ == '__main__':
  _, _ = map(int, input().strip().split())
  S = input().strip().split()
  T = input().strip().split()
  # S = range(1000)
  # T = range(1000)
  print(main(S, T))

### FIXED CODE ###

MOD = 10 ** 9 + 7


def main(S, T):
  l = len(T) + 1
  dp = [0] * l
  # sdp = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]

  # for i, s in enumerate(S):
  #  for j, t in enumerate(T):
  #    v = sdp[i][j + 1] + sdp[i + 1][j] + (1 if s == t else -sdp[i][j])
  #    sdp[i + 1][j + 1] = v % MOD
  for i, s in enumerate(S):
    tmp = [0] * l
    for j, t in enumerate(T):
      v = dp[j + 1] + tmp[j] + (1 if s == t else -dp[j])
      tmp[j + 1] = v % MOD
    dp = tmp

  # return (sdp[-1][-1] + 1)
  return dp[-1] + 1


if __name__ == '__main__':
  if True:
    _, _ = map(int, input().strip().split())
    S = input().strip().split()
    T = input().strip().split()
  else:
    S = range(1000)
    T = range(1000)
  print(main(S, T))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

import itertools


def mostProperComb(childs, x):
    tmp_sum = sum([c[1] for c in childs])
    if tmp_sum > x:
        print("IMPOSSIBLE")
        exit()

    total = tmp_sum + sum([c[0] for c in childs])

    max_a, min_b = 0, 0
    for code in itertools.product([True, False], repeat=len(childs)):
        a = 0
        for j, bool in enumerate(code):
            if bool:
                a += childs[j][1]
            else:
                a += childs[j][0]
        if a >= max_a and x >= a:
            max_a, min_b = a, total - a
            if max_a == x:
                break

    return (max([x, min_b]), min([x, min_b]))


n = int(input())

p_list = [0] + list(map(int, input().split()))
x_list = list(map(int, input().split()))
c_list = [[] for i in range(n)]

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

for i in range(n):
    index = n - 1 - i

    if len(c_list[index]) == 0:
        c_list[index] = (x_list[index], 0)
        c_list[p_list[index] - 1].append(index)
    else:
        childs = [c_list[child_index] for child_index in c_list[index]]
        c_list[index] = mostProperComb(childs, x_list[index])
        if not p_list[index] == 0:
            c_list[p_list[index] - 1].append(index)

print("POSSIBLE")


### FIXED CODE ###

# -*- coding: utf-8 -*-

import itertools


def mostProperComb(childs, x):
    tmp_sum = sum([c[1] for c in childs])
    if tmp_sum > x:
        print("IMPOSSIBLE")
        exit()

    total = tmp_sum + sum([c[0] for c in childs])

    sset = set([tmp_sum])
    for child in childs:
        rest = child[0] - child[1]
        tmp_set = set(sset)
        for s in sset:
            if s + rest <= x:
                tmp_set.add(s+rest)
        sset = tmp_set

    return (tuple(sorted([x, total-max(sset)], reverse=True)))


n = int(input())

p_list = [0] + list(map(int, input().split()))
x_list = list(map(int, input().split()))
c_list = [[] for i in range(n)]

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

for i in range(n):
    index = n-1-i

    if len(c_list[index]) == 0:
        c_list[index] = (x_list[index], 0)
        c_list[p_list[index]-1].append(index)
    else:
        childs = [c_list[child_index] for child_index in c_list[index]]
        c_list[index] = mostProperComb(childs, x_list[index])
        if not p_list[index] == 0:
            c_list[p_list[index]-1].append(index)

print("POSSIBLE")
### BUGGY CODE ###

n,x,y = map(int,input().split())
INF = 10**5
d = [[INF]*n for _ in range(n)]
def wf(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j],d[i][k] + d[k][j])

for i in range(n-1):
  d[i][i+1] = 1
  d[i+1][i] = 1
  
d[x-1][y-1]=1
d[y-1][x-1]=1
wf(d)

ans = [0]*(n-1)
for i in range(n-1):
  for j in range(i+1,n):
    ans[d[i][j]-1]+=1

for a in ans:
  print(a)

### FIXED CODE ###

n,x,y = map(int,input().split())
x,y = x-1,y-1
ans = [0]*(n)

for i in range(n):    
  for j in range(i+1,n):
    sp = min(abs(j-i), abs(x-i)+abs(j-y)+1, abs(y-i)+1+abs(j-x))
    ans[sp]+=1
    
for a in ans[1:]:
  print(a)
### BUGGY CODE ###

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

res = -1

for i in range(N):
    p[i] = (p[i]+1)/2
    if i+1 < K:
        continue
    val = sum(p[i+1-K:i+1])
    if val > res:
        res = val

print(res)


### FIXED CODE ###

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

for i in range(N):
    p[i] = (p[i]+1)/2

sum_list = [0] * N

for i in range(N):
    if i == 0:
        sum_list[i] = p[i]
    else:
        sum_list[i] = sum_list[i-1]+p[i]
res = sum_list[K-1]

for i in range(N):
    if i < K:
        continue
    if sum_list[i] - sum_list[i-K] > res:
        res = sum_list[i] - sum_list[i-K]

print(res)
### BUGGY CODE ###

n, m = map(int, input().split())
X = [int(x) for x in input().split()]
Y = [int(x) for x in input().split()]
p = 10 ** 9 + 7
S = [[(X[i + 1] - X[i]) * (Y[j + 1] - Y[j]) for j in range(m - 1)] for i in range(n - 1)]
for i in range(n - 1):
  for j in range(m - 1):
    S[i][j] *= (n - i - 1) * (i + 1)
    #S[i][j] %= p
    S[i][j] *= (m - j - 1) * (j + 1)
    #S[i][j] %= p
print(sum([sum(s) for s in S]) % p)

### FIXED CODE ###

n, m = map(int, input().split())
p = 10 ** 9 + 7
X = [int(x) for x in input().split()]
Y = [int(x) for x in input().split()]
XX = [(X[i + 1] - X[i]) * (n - i - 1) * (i + 1) % p for i in range(n - 1)]
YY = [(Y[j + 1] - Y[j]) * (m - j - 1) * (j + 1) % p for j in range(m - 1)]
print(sum(XX) * sum(YY) % p)
### BUGGY CODE ###

n = int(input())

tt = list(map(int, input().split()))
v = list(map(int, input().split()))

time = sum(tt);

border = [0] *(n+1)
start_v = [0] *(n+1)
end_v = [0] *(n+1)

temp = 0
for i in range(n):
	temp += tt[i]
	border[i+1] = temp
	start_v[i] = v[i]
	end_v[i+1] = v[i]

t = 0
idx = 0
ans = 0
vlast = 0
v0 = 0
v_list = []

# print (border)
while t < time :
	v_list = []
	t += 0.5

	#直接制約
	v_list.append(v[idx])
	if t == border[idx+1]:
		idx += 1
#		v0 = min(v0, v[idx])

	for j in range(n+1):
		
		if border[j] <= t:
			#前の時刻からの制約
			temp = end_v[j] + (t - border[j])
			v_list.append(temp)
			# if v0 > temp:
			# 	v0 = temp
		if border[j] >= t:
			#後ろの時刻からの制約
			temp = start_v[j] + (border[j] - t)
			v_list.append(temp)
			# if v0 > temp:
			# 	v0 = temp

	v0 = min(v_list)
#	print(v0)

#	ans += 0.5 * (vlast + v0) / 2
	ans += (vlast + v0)
	vlast = v0

ans /= 4.0
print (ans)



### FIXED CODE ###

n = int(input())

tt = list(map(int, input().split()))
v = list(map(int, input().split()))

time = sum(tt);
INF = 999999
border = [0] *(n+1)
start_v = [0] *(n+1)
end_v = [0] *(n+1)

temp = 0
for i in range(n):
	temp += tt[i]
	border[i+1] = temp
	start_v[i] = v[i]
	end_v[i+1] = v[i]

t = 0
idx = 0
ans = 0
vlast = 0
v0 = 0
new_interval = False
limitation_front =0 # 最初の計算に必要

# print (border)
while t < time :
	t += 0.5
	new_interval = False

	#直接制約
	v0 = v[idx]
	if t == border[idx+1]:
		idx += 1
		new_interval = True
#		v0 = min(v0, v[idx])

	if(not new_interval):
		limitation_front += 0.5
		if v0 > limitation_front:
			v0 = limitation_front
	
	if new_interval: 
		limitation_front = INF
		for j in range(n+1):
			if border[j] <= t:
				#前の時刻からの制約
				temp = end_v[j] + (t - border[j])
				if v0 > temp:
					v0 = temp
				if limitation_front > temp:
					limitation_front = temp
			else:
				break
			#print (limitation_front)


	for j in range(n+1):
		if border[j] >= t:
			#後ろの時刻からの制約
			temp = start_v[j] + (border[j] - t)
			if v0 > temp:
				v0 = temp

	#print(v0)

#	ans += 0.5 * (vlast + v0) / 2
	ans += (vlast + v0)
	vlast = v0

ans /= 4.0
print (ans)
### BUGGY CODE ###

import itertools

N, M, R = map(int, input().split())
r = list(map(int, input().split()))
INF = 10**10
dp = [[INF for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    A, B, C = map(int, input().split())
    dp[A][B] = C
    dp[B][A] = C

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

ans = 10**10
for route in itertools.permutations(r):
    total = 0
    for i in range(R-1):
        total += dp[route[i]][route[i+1]]
    ans = min(ans, total)
print(ans)


### FIXED CODE ###

import heapq
import itertools

def dijkstra(s):
    cost = [10**20] * (N+1)
    visited = [False] * (N+1)
    visited[s], cost[s] = True, 0
    q = []

    for r in route[s]:
        heapq.heappush(q, r)

    while q:
        c, r = heapq.heappop(q)

        if not visited[r]:
            visited[r] = True
            cost[r] = min(cost[r], c)

            for c_, n in route[r]:
                if not visited[n]:
                    heapq.heappush(q, (c+c_, n))

    return cost

N, M, R = map(int, input().split())
r_ = list(map(int, input().split()))
ans = 10**10
route = [[] for i in range(N+1)]

for i in range(M):
    A, B, C = map(int, input().split())
    route[A].append((C, B))
    route[B].append((C, A))

cost = {r:dijkstra(r) for r in r_}
for r in itertools.permutations(r_):
    total = 0

    for i in range(R-1):
        total += cost[r[i]][r[i+1]]
    ans = min(ans, total)
print(ans)
### BUGGY CODE ###

import numpy as np
from math import factorial

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

dic = {}
after = {}

newdata = np.unique(A)
for i in range(len(newdata)):
	x = np.sum(A == newdata[i])
	if x <= 1:
		dic[newdata[i]] = 0
	else:
		dic[newdata[i]] = x * (x - 1) // 2
	if x - 1 <= 1:
		after[newdata[i]] = 0
	else:
		after[newdata[i]] = (x - 1) * (x - 2) // 2

numsum = 0
for dicv in dic.values():
	numsum += dicv 


for i in range(N):
	print(int(numsum - dic[A[i]] + after[A[i]]))



### FIXED CODE ###

import numpy as np
import collections

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

dic = {}
after = {}

l = collections.Counter(A)

for key, val in l.items():
	dic[key] = val * (val - 1) // 2
	after[key] = (val - 1) * (val - 2) // 2

numsum = sum(dic.values())

ans = {}
for key in dic.keys():
	ans[key] = numsum - dic[key] + after[key]

for i in range(N):
	print(ans[A[i]])