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

import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze += [list(readline().rstrip().decode())]
visited = [[10**9]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)

### FIXED CODE ###

import sys
import heapq
push = heapq.heappush
pop = heapq.heappop
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
 
H,W = map(int,readline().split())
sh,sw = map(int,readline().split())
gh,gw = map(int,readline().split())
sh,sw = sh-1,sw-1
gh,gw = gh-1,gw-1
maze = []
for _ in range(H):
    maze.append(readline().rstrip().decode())
visited = [[10**6]*W for _ in range(H)] #必要な最小ワープ回数
hp = []
push(hp,(0,sh,sw))
visited[sh][sw] = 0
while hp:
    rp,h,w = pop(hp)
    if visited[h][w] < rp:
        continue
    if h == gh and w == gw:
        print(rp)
        exit()
    for i in range(5):
        for j in range(5):
            if i == 2 and j == 2:
                continue
            if 0 <= h+i-2 < H and 0 <= w+j-2 < W:
                if maze[h+i-2][w+j-2] == ".":
                    if abs(i-2)+abs(j-2) <= 1:
                            if visited[h+i-2][w+j-2] > rp:
                                push(hp,(rp,h+i-2,w+j-2))
                                visited[h+i-2][w+j-2] = rp
                    else:
                        if visited[h+i-2][w+j-2] > rp+1:
                            push(hp,(rp+1,h+i-2,w+j-2))
                            visited[h+i-2][w+j-2] = rp+1
print(-1)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(200000000)


# my functions here!
#繰り返し自乗法だよ
#これはnのp乗をmで割ったあまりをだすよ
def modular_w_binary_method (n,m,p):
    ans=1 if n>0 else 0
    while(p>0):
        if p%2==1:
            ans=(ans*n)%m
        n=(n**2)%m
        p//=2
    return ans

#mod上でのaの逆元を出すよ
"""
    フェルマーの小定理より a**(p)%p==a isTrue
    これを利用すれば a**(p-2)%p==a**(-1) isTrue
    元と逆元とをかけてpで割れば1が余るよ！
"""
def modular_inverse(a,prime):
    return(modular_w_binary_method(a,prime,prime-2))


#逆元を使うと容易に頑張れるｃ
def conbination(n,a,mod=10**9+7):
    #cはイラない
    res=1 
    for s in range(a):
        res=(res*(n-s)*(modular_inverse(s+1,mod)))%mod

        
    return res
#操作から作れるものの組み合わせは何個かー＞同じものでも違う方法で構成できるかから考える方法もある
#入力

def pin(type=int):
    return map(type,input().rstrip().split())
    
def resolve():
    N,=pin()
    A=list(pin())
    S=[sum(A[:i])for i in range(N+1)]
    from collections import Counter
    s=list(Counter(S).values())
    ans=0
    for j in s:
        if j>1:
            ans+=conbination(j,2)
    print(ans)
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """6
1 3 -4 2 2 -2"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """7
1 -1 1 -1 1 -1 1"""
        output = """12"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5
1 -2 3 -4 5"""
        output = """0"""
        self.assertIO(input, output)

if __name__=="__main__":resolve()

### FIXED CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(200000000)


# my functions here!

#入力

def pin(type=int):
    return map(type,input().rstrip().split())
from collections import Counter
from itertools import accumulate as acm
def resolve():
    N,=pin()
    S=list(acm(pin()))
    S.insert(0,0)
    s=list(Counter(S).values())
    ans=0
    for j in s:
            ans+=(j*(j-1))//2
    print(ans)
"""
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
if __name__=="__main__":resolve()
### BUGGY CODE ###

N, M = map(int, input().split())
print(max(d for d in range(1, M // N + 1) if M % d == 0))


### FIXED CODE ###

N, M = map(int, input().split())
print(next(d for d in reversed(range(M // N + 1)) if M % d == 0))
### BUGGY CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N,M=LI()
RES = [-1]*(N+1)
RES[N] = 0.0

MP=[[] for i in range(N+1)]
for _ in range(M):
    i, j = LI()
    MP[i].append(j)

for i in range(N-1, 0, -1):
    div = len(MP[i])
    next_E = 0
    for j in MP[i]: next_E += RES[j] + 1
    RES[i] = next_E / div

result = RES[1]
RESN = [0]*(N+1)

for i in range(1, N-1):
    if len(MP[i]) == 1: continue

    max_j = max((RES[w],w) for w in MP[i])[1]
    for k in range(N-1, 0, -1):
        div = 0
        next_E = 0
        for j in MP[k]:
            if k != i or j != max_j:
                div += 1
                next_E += RESN[j] + 1
        RESN[k] = next_E / div
    result = min(result, RESN[1])

print(result)


### FIXED CODE ###

def resolve():
    n,m=map(int,input().split())
    edges=[[] for _ in range(n)]
    for _ in range(m):
        s,t=map(int,input().split())
        s-=1; t-=1
        edges[s].append(t)
 
    # 確率DP
    p=[0]*n
    p[0]=1.0
    for v in range(n):
        for nv in edges[v]:
            p[nv]+=p[v]/len(edges[v])
 
    # 期待値DP
    E=[0]*n
    for v in range(n-2,-1,-1):
        for nv in edges[v]:
            E[v]+=E[nv]
        E[v]=1+E[v]/len(edges[v])
 
    ans=E[0]
    for v in range(n):
        if(len(edges[v])<=1): continue
        # 各vに対して、辺vwのうちE[w]が最大のものを削除する
        w=max(*((E[w],w) for w in edges[v]))[1]
        dE=0
        deg=len(edges[v])
        for nv in edges[v]:
            if(nv==w): dE-=E[nv]/deg
            else: dE+=E[nv]/(deg-1)/deg
        ans=min(ans,E[0]+p[v]*dE)
 
    print(ans)
resolve()
### BUGGY CODE ###

import sys
from collections import deque
import copy
import numpy


readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start,ex_kyori):
    tansaku = deque()
    tansaku.append(start)
    visited = {i:set() for i in range(h)}
    kyori = copy.deepcopy(ex_kyori)
    while tansaku:
        pre_y,pre_x = tansaku.popleft()
        if pre_x in visited[pre_y]:
            continue
        for i in range(pre_x-1,pre_x+2,2):
            if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                tansaku.append([pre_y,i])
                kyori[pre_y][i] = min(kyori[pre_y][i],kyori[pre_y][pre_x]+1)
        for j in range(pre_y-1,pre_y+2,2):
            if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                tansaku.append([j,pre_x])
                kyori[j][pre_x] = min(kyori[j][pre_x],kyori[pre_y][pre_x]+1)
        visited[pre_y].add(pre_x)
    return kyori

h,w = nm()
tizu = []
sharp = []
saitan = [[10**10]*w for _ in range(h)]
saitan = numpy.array(saitan)
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
for i,j in sharp:
    saitan[i][j] = 0 
for i in sharp:
    saitan = bfs(i,saitan)
print(numpy.max(saitan))

### FIXED CODE ###

import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start):
    tansaku = deque(start)
    visited = {i:set() for i in range(h)}
    res = 0
    black = len(start)
    while black != h*w:
        for _ in range(len(tansaku)):
            pre_y,pre_x = tansaku.popleft()
            if pre_x in visited[pre_y]:
                continue
            for i in range(pre_x-1,pre_x+2,2):
                if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                    tansaku.append([pre_y,i])
                    tizu[pre_y][i] = '#'
            for j in range(pre_y-1,pre_y+2,2):
                if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                    tansaku.append([j,pre_x])
                    tizu[j][pre_x] = '#'
            visited[pre_y].add(pre_x)
        black += len(tansaku)
        res += 1
    return res

h,w = nm()
tizu = []
sharp = []
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
ans = bfs(sharp)
print(ans)
### BUGGY CODE ###

def main():
	a,b,c,d = map(int,input().split())
	ans = 0
	i = int(a/c)
	t = int(a/d)
	while i*c < a:
		i += 1
	while t*d < a:
		t += 1
	ans_set = set()

	while a <= i * c <= b:
		ans_set.add(i*c)
		i += 1

	while a <= t * d <= b:
		ans_set.add(t*d)
		t += 1
	print(int(len(range(a,b+1)))-len(ans_set))

if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
	a,b,c,d = map(int,input().split())

	#about c
	ans_c_a = (a-1)//c
	ans_c_b = b//c
	# print(ans_c_b)
	ans_c = ans_c_b - ans_c_a
	# print("ans_c = {}".format(ans_c))

	#about d
	ans_d_a = (a-1)//d
	ans_d_b = b//d
	ans_d = ans_d_b - ans_d_a
	# print("ans_d = {}".format(ans_d))

	#aboud c*d
	import fractions
	saisyou = (c * d) // fractions.gcd(c,d)
	# print(saisyou)
	ans_saisyou_a = (a-1)//saisyou
	ans_saisyou_b = b//saisyou
	ans_saisyou = ans_saisyou_b - ans_saisyou_a
	# print("ans_saisyou = {}".format(ans_saisyou))

	print(int( b-a+1 - (ans_c + ans_d - ans_saisyou) ))


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

import numpy
H, W, D = map(int, input().split())
A = numpy.array([list(map(int, input().split())) for i in range(H)])
Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]

num_dict = {}
y = 0
for aa in A:
    x = 0
    for a in aa:
        num_dict[a] = [x, y]
        x += 1
    y += 1

for l, r in LR:
    ans = 0
    z = l
    while z != r:
        zahyo1 = num_dict[z]
        x1, y1 = int(zahyo1[0]), int(zahyo1[1])
        zahyo2 = num_dict[z+D]
        x2, y2 = int(zahyo2[0]), int(zahyo2[1])
        ans += (abs(x1-x2)+abs(y1-y2))
        z = z + D
    print(ans)

### FIXED CODE ###


H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]
d = [0] * ((H*W)+1)
num_dict = {}
y = 0
for aa in A:
    x = 0
    for a in aa:
        num_dict[a] = [x, y]
        x += 1
    y += 1

for i in range(D+1, H*W+1):
    d[i] = d[i-D] + abs(num_dict[i][0]-num_dict[i-D][0]) + abs(num_dict[i][1]-num_dict[i-D][1])
for l, r in LR:
    print(d[r]-d[l])
### BUGGY CODE ###

S = input()
ans = 0
for j in range(len(S)):
    for i in range(j+1):
        if int(str(S[i:j+1])) % 2019 == 0:
            ans += 1
print(ans)


### FIXED CODE ###

import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]

S = deque(map(int, list(input())))
num = 0
dict = {}
dict[0] = 1
ans = 0

for i in range(len(S)):
    num += S.pop() * pow(10,i,2019)
    cand = num % 2019
    if cand in dict.keys():
        dict[cand] += 1
    else:
        dict[cand] = 1

for key in dict.keys():
    ans += dict[key] * (dict[key] - 1) // 2
print(ans)
### BUGGY CODE ###

s = input()
length = len(s)
count_dict = {}

num = int(s)%2019
count_dict[num] = 1

for i in range(1,length):
    num = (num-int(s[-i])*10**(i-1)%2019)%2019
    # num = num+int(s[-i])
    if num not in count_dict:
        count_dict[num] = 1
    else:
        count_dict[num] += 1


count = 0
for k,v in count_dict.items():
    count += v*(v-1)/2
    if k == 0:
        count += v

print(int(count))

### FIXED CODE ###

s = input()
length = len(s)
count_dict = {}

'''for i in range(length-4):
    for j in range(i+4,length+1):
        num = int(s[i:j])
        if num%2019 == 0:
            count += 1'''

num = int(s)%2019
count_dict[num] = 1

# num = int(s[-1])
# count_dict[num] = 1

for i in range(1,length):
    num = (num-int(s[-i])*pow(10,(i-1),2019))%2019
    # num = num+int(s[-i])
    if num not in count_dict:
        count_dict[num] = 1
    else:
        count_dict[num] += 1


count = 0
for k,v in count_dict.items():
    count += v*(v-1)/2
    if k == 0:
        count += v

print(int(count))
### BUGGY CODE ###

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

i=0
while i<k:
  if a>0:
    a=a-1
    i=i+1
  elif b>0:
    b=b-1
    i=i+1
print(a,b)
  

### FIXED CODE ###

a, b, k = map(int,input().split())
if k >= a + b:
  print("0 0")
elif k>a:
  print ("0 "+str(a+b-k))
else:
  print(str(a-k)+" "+str(b))
### BUGGY CODE ###

Q = int(input())

import heapq
import sys
input = sys.stdin.readline

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -heapq.nsmallest(1,L)[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

for _ in range(Q):
  q = [int(x) for x in input().split()]
  if q[0]&1:
    f1(q[1],q[2])
  else:
    f2()


### FIXED CODE ###

Q = int(input())

import heapq
import sys
input = sys.stdin.readline

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -L[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

QUERY = [[int(x) for x in input().split()] for _ in range(Q)]
for q in QUERY:
  if q[0]&1:
    f1(q[1],q[2])
  else:
    f2()
### BUGGY CODE ###

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

ans = 1
t = 10 ** 18
for i in range(n):
    if a[i] == 0:
        print(0)
        exit(0)
    ans *= a[i]

if ans <= t:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

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

ans = 1
t = 1e18
if 0 in a:
    print(0)
    exit(0)

for i in range(n):
    ans *= a[i]
    if ans > t:
        print(-1)
        exit(0)

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

K = int(input())

def lunlun(n):
    x = str(n)
    if len(x)==1:
        return True
    else:
        for i in range(len(x)-1):
            if abs(int(x[i])-int(x[i+1]))>1:
                return False
        else:
            return True

i = 0
j = 1
while i<K:
  if lunlun(j):
    i +=1
  j += 1

print(j-1)

### FIXED CODE ###

from collections import deque
import sys
K = int(input())
q = deque([1,2,3,4,5,6,7,8,9])
num = 0
if K<=9:
    print(q[K-1])
    sys.exit()
for i in range(10**5):
    p = q.popleft()
    num += 1
    if num == K:
        print(p)
    if p%10 != 0:
        q.append(p*10+p%10-1)
    q.append(p*10+p%10)
    if p%10 != 9:
        q.append(p*10+p%10+1)
### BUGGY CODE ###

def main():
    k, s = map(int,input().split())
    ans = 0
    for i in range(k+1):
        for j in range(k+1):
            for l in range(k+1):
                if j+i+l == s:
                    ans += 1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    k, s = map(int,input().split())
    ans = 0
    for i in range(k+1):
        for j in range(k+1):
            if i+j <= s and s-i-j <= k:
                ans += 1
    print(ans)

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

n = int(input())
la = list(map(int, input().split()))
q = int(input())
ls = sum(la)
lc = []
lc_cnt = []
for i in range(q):
  b, c = map(int, input().split())
  cnt = la.count(b)
  if lc.count(b) > 0:
    j = 0
    for k in lc:
      cnt += lc_cnt[j] if k == b else 0
      j += 1
  ls += (c-b)*cnt
  
  lc.append(c)
  lc_cnt.append(cnt)
  print(ls)

### FIXED CODE ###

n = int(input())
la = list(map(int, input().split()))
sa = sum(la)
l_cnt = [0]*100001
for i in la:
  l_cnt[i] += 1
q = int(input())
for i in range(q):
  b, c = map(int, input().split())
  sa += (c-b)*l_cnt[b]
  print(sa)  
  l_cnt[c] += l_cnt[b]
  l_cnt[b] = 0
### BUGGY CODE ###

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

for i in range(N):
    if P[i] <= min(P[0: i + 1]):
        answer += 1
print(answer)


### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
answer = 0
minimum = P[0]

for i in range(N):
    if P[i] <= minimum:
        answer += 1
    minimum = min(P[i], minimum)
print(answer)
### BUGGY CODE ###

n=int(input())
b=[[]for _ in range(n)]
d=[]
inf=float('inf')
for i in range(n):
  s=input()
  c=[]
  for j in range(n):
    if s[j]=="1":
      b[i]+=[(i,j)]
    c.append(1 if s[j]=="1" else inf)
  d.append(c)
from scipy.sparse.csgraph import bellman_ford
d=bellman_ford(d)
x=[-1]*n
x[0]=0
Q=b[0]
while Q:
  p=[]
  for i,j in Q:
    if x[j]<0:
      x[j]=x[i]^1
      p+=b[j]
    elif x[i]==x[j]:print(-1);exit()
  Q=p
print(int(max(map(max,*d)))+1)

### FIXED CODE ###

n=int(input())
b=[[]for _ in range(n)]
d=[]
inf=float('inf')
inf=float('inf')
for i in range(n):
  s=input()
  c=[]
  for j in range(n):
    if s[j]=="1":
      b[i]+=[(i,j)]
    c.append(1 if s[j]=="1" else inf)
  d.append(c)
def warshall_floyd(d):
    for i in range(n):d[i][i]=0
    #d[i][j]: iからjへの最短距離
    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])
    return d
d=warshall_floyd(d)
x=[-1]*n
x[0]=0
Q=b[0]
while Q:
  p=[]
  for i,j in Q:
    if x[j]<0:
      x[j]=x[i]^1
      p+=b[j]
    elif x[i]==x[j]:print(-1);exit()
  Q=p
z=0
for i in d:
  for j in i:
    if j!=float("inf"):z=max(j,z)
print(z+1)
### BUGGY CODE ###

n,x,y = map(int,input().split())
x -= 1
y -= 1
dis = [[0 for i in range(n)]for j in range(n)]
for i in range(n):
    for j in range(n):
        dis[i][j] = min(abs(j-i),min(abs(j-y)+abs(x-i)+1,abs(j-x)+abs(y-i)+1))
d = [0 for i in range(n)]
for i in range(n):
    for j in range(n):
        d[dis[i][j]] += 1
d = list(map(lambda x:x//2,d))
print("\n".join(map(str,d[1:])))

### FIXED CODE ###

n,x,y = map(int,input().split())
x -= 1
y -= 1
dis = [0 for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        dis[min(abs(j-i),min(abs(j-y)+abs(x-i)+1,abs(j-x)+abs(y-i)+1))] += 1
print("\n".join(map(str,dis[1:])))
### BUGGY CODE ###

import math
r,g,b,n = map(int, input().split())
count = 0
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()
ans = 0
while True:
    beore = len(S)
    S = S.replace('01', '').replace('10','')
    after = len(S)
    if beore == after:
        break
    else:
        ans += beore-after
print(ans)

### FIXED CODE ###

S = input()
ans = 2*min(S.count('0'),S.count('1'))
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
A = [int(a) for a in input().split()]
for _ in range(M):
    B,C = map(int,input().split())
    A += [C]*B
A.sort(reverse=True)
print(sum(A[:N]))


### FIXED CODE ###

N,M = map(int,input().split())
A = [int(a) for a in input().split()]
BC = [[int(x) for x in input().split()] for _ in range(M)]

BC.sort(key=lambda x:x[1], reverse=True)

count = 0
Added_list = []
for i in range(M):
    B,C = BC[i]
    Added_list += [C]*B
    count += B
    if count>N:
        Added_list = Added_list[:N]
        break

A += Added_list
A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(lambda i: (i + 1) / 2, list(map(int, input().split()))))
# print(p)
lists = [sum(p[i:i + k]) for i in range(n - k + 1)]
print('{0:.10f}'.format(max(lists)))

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(lambda i: (i + 1) / 2, list(map(int, input().split()))))
suma = sum(p[0:k]) 
max = suma
for i in range(k, n):
    suma += (p[i] - p[i - k])
    if suma > max:
        max = suma

print('{:.8f}'.format(max))