Harryxun/stf_run huggingface dataset:
import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa.pop(i)
        if not c == 0:
            if aa[c-1][v] > aa[c][v]+1:
                aa[c-1][v] = aa[c][v]+1
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] > aa[c][v]+1:
                aa[c+1][v] = aa[c][v]+1
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] > aa[c][v]+1:
                aa[c][v-1] = aa[c][v]+1
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] > aa[c][v]+1:
                aa[c][v+1] = aa[c][v]+1
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)
        


### FIXED CODE ###

import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa[i]
        if not c == 0:
            if aa[c-1][v] > aa[c][v]+1:
                aa[c-1][v] = aa[c][v]+1
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] > aa[c][v]+1:
                aa[c+1][v] = aa[c][v]+1
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] > aa[c][v]+1:
                aa[c][v-1] = aa[c][v]+1
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] > aa[c][v]+1:
                aa[c][v+1] = aa[c][v]+1
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)
N, M, K = [int(i) for i in input().split()]

As = [int(i) for i in input().split()]
Bs = [int(i) for i in input().split()]

cnt = 0
time = 0
while time <= K:
    cnt += 1
    if As and Bs:
        if As[0] > Bs[0]:
            p = Bs.pop(0)
        elif Bs[0] > As[0]:
            p = As.pop(0)
    else :
        if As:
            p = As.pop(0)
        elif Bs:
            p = Bs.pop(0)
        else :
            break
    time += p
    
print(cnt - 1)

### FIXED CODE ###

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

array_A = [int(i) for i in input().split()]
array_B = [int(i) for i in input().split()]

array_A_2 = [0]
array_B_2 = [0]

for a in array_A:array_A_2.append(array_A_2[- 1]+a)
for b in array_B:array_B_2.append(array_B_2[- 1]+b)

output, j = 0, M

for i in range(N + 1):
    if array_A_2[i] > K:
        break
    while array_B_2[j] > K - array_A_2[i]:
        j -= 1
    output = max(output, i + j)

print(output)
import queue

def resolve():
    # ★get input
    h, w = map(int, input().split())

    grid = [["" for i in range(w)] for j in range(h)]

    for i in range(h):
        line = list(input())
        for j in range(w):
            grid[i][j] = line[j]

    # ★exec
    # BFSにて最短経路を求める
    # 準備
    distance = [[-1 for i in range(w)] for j in range(h)]
    que = queue.Deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                que.put([i, j])
                distance[i][j] = 0

    # BFS開始
    while not que.empty():

        now = que.get()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = [now[0] + move_y, now[1] + move_x]
            if not h > target[0] >= 0 or not w > target[1] >= 0:
                continue

            # 黒塗りされているなら何もしない
            if grid[target[0]][target[1]] == '#':
                continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            que.put(target)

            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
s = input().split()
w = int(s[1])/2
print(int((s[0])+w)

### FIXED CODE ###

s = input().split()
N = int(s[0])
W = int(s[1])/2
print(int(N+W))
H, W, M = map(int, input().split())
Bom = [[0] * W for _ in range(H)]
BomC = [0] * W
BomR = [0] * H
for _ in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    Bom[h][w] = 1
    BomC[w] += 1
    BomR[h] += 1

C = []
R = []
ans = 0

for w, c in enumerate(BomC):
    C.append((c, w))
for h, r in enumerate(BomR):
    R.append((r, h))
C.sort(reverse=True)
R.sort(reverse=True)
cm = max(BomC)
rm = max(BomR)

for r, h in R:
    if r < rm - 1:
        break
    for c, w in C:
        if c < cm - 1:
            break
        ans = max(ans, r + c - Bom[h][w])

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

H, W, M = map(int, input().split())

X = [0] * W
Y = [0] * H
Map = []

for _ in range(M):
    h, w = map(int, input().split())
    h -= 1
    w -= 1
    Y[h] += 1
    X[w] += 1
    Map.append((h, w))

MX = max(X)
MY = max(Y)
ans = MX + MY
Xans = set()
Yans = set()
for i, x in enumerate(X):
    if x == MX:
        Xans.add(i)
for i, y in enumerate(Y):
    if y == MY:
        Yans.add(i)
cnt = 0
for h, w in Map:
    if h in Yans and w in Xans:
        cnt += 1
if cnt == len(Xans) * len(Yans):
    ans -= 1
print(ans)
s = input()[::-1]
s = s.replace("maerd", "", 1)

while True:
    end_flg = False
    if s[:5] == "maerd":
        s = s.replace("maerd", "", 1)
        end_flg = True
        print(s)
    elif s[:5] == "esare":
        s = s.replace("esare", "", 1)
        end_flg = True
    elif s[:7] == "remaerd":
        s = s.replace("remaerd", "", 1)
        end_flg = True
    elif s[:6] == "resare":
        s = s.replace("resare", "", 1)
        end_flg = True    

    if end_flg == False:
        break
        
if s == "":
    print("YES")
else:
    print("NO")

### FIXED CODE ###

s = input()[::-1]
while True:
    end_flg = False
    if s[:5] == "maerd":
        s = s.replace("maerd", "", 1)
        end_flg = True
    elif s[:5] == "esare":
        s = s.replace("esare", "", 1)
        end_flg = True
    elif s[:7] == "remaerd":
        s = s.replace("remaerd", "", 1)
        end_flg = True
    elif s[:6] == "resare":
        s = s.replace("resare", "", 1)
        end_flg = True    

    if end_flg == False:
        break
        
if s == "":
    print("YES")
else:
    print("NO")
yohou = input().rstrip().split("")
tenki = input().rstrip().split("")
 
tekichu = 0
 
for i in range(3):
	if yohou[i] == tenki[i]:
		tekichu += 1
 
print(tekichu)

### FIXED CODE ###

s = list(input())
t = list(input())

cnt = 0
for i in range(3):
  if s[i] == t[i]:
    cnt += 1

print(cnt)
N = int(input())
reds = sorted([list(map(int,input().split())) for i in range(n)])
blues = sorted([list(map(int,input().split())) for i in range(n)])

reds = reds[::-1]
res = 0

for c,d in blues:
  for a,b in reds:
    if a<c and b<d:
      reds.remove([a,b])
      res+=1
      break
      
print(res)


### FIXED CODE ###

n = int(input())
reds = sorted([list(map(int,input().split())) for i in range(n)],key=lambda reds: -reds[1])
blues = sorted([list(map(int,input().split())) for i in range(n)])

res = 0

for c,d in blues:
  for a,b in reds:
    if a<c and b<d:
      reds.remove([a,b])
      res+=1
      break
      
print(res)
W,H,N = 5,4,3
s = set([])
for h in range(H):
    for w in range(W):
        s.add((w+0.5, h+0.5))
# print(s)

for _  in range(N):
    x,y,a = map(int, input().split())
    rm = set([])
    if a==1:
        for si in s:
            if si[0]<x: rm.add(si)
    if a==2:
        for si in s:
            if si[0]>x: rm.add(si)
    if a==3:
        for si in s:
            if si[1]<y: rm.add(si)
    if a==4:
        for si in s:
            if si[1]>y: rm.add(si)
    s = s - rm
                
print(len(s))

### FIXED CODE ###

W,H,N = map(int, input().split())
s = set([])
for h in range(H):
    for w in range(W):
        s.add((w+0.5, h+0.5))
# print(s)

for _  in range(N):
    x,y,a = map(int, input().split())
    rm = set([])
    if a==1:
        for si in s:
            if si[0]<x: rm.add(si)
    if a==2:
        for si in s:
            if si[0]>x: rm.add(si)
    if a==3:
        for si in s:
            if si[1]<y: rm.add(si)
    if a==4:
        for si in s:
            if si[1]>y: rm.add(si)
    s = s - rm
                
print(len(s))
n,k=map(int, input().split())
x=list(map(int, input().split()))
zi=0
for xi in x:
    if xi>=0:
        break
    zi+=1

xm=[0]
if x[zi]==0:
    xp=[]
else:
    xp=[0]

xm.extend(reversed(x[:zi]))
xp.extend(x[zi:])

ans=float('inf')
for i in range(k):
    if i<len(xm) and k-i<len(xp):
        ans=min(xm[i]*2*(-1) + xp[k-i], ans)
    if i<len(xp) and k-i<len(xm):
        ans=min(xp[i]*2 + xm[k-i]*(-1), ans)
if len(x)==1 and x[0]==0:
    ans=0
print(ans)

### FIXED CODE ###

n,k=map(int, input().split())
x=list(map(int, input().split()))
zi=0
for xi in x:
    if xi>=0:
        break
    zi+=1

xm=[0]
if zi<len(x) and x[zi]==0:
    xp=[]
else:
    xp=[0]

xm.extend(reversed(x[:zi]))
xp.extend(x[zi:])

ans=float('inf')
for i in range(k):
    if i<len(xm) and k-i<len(xp):
        ans=min(xm[i]*2*(-1) + xp[k-i], ans)
    if i<len(xp) and k-i<len(xm):
        ans=min(xp[i]*2 + xm[k-i]*(-1), ans)
if len(x)==1 and x[0]==0:
    ans=0
print(ans)
N = int(input().split())
d = list(map(int, input().split()))

d.sort()

if d[int((N-1)/2)] == d[int(N/2)]:
    result = 0
else:
    result = d[int(N/2)]-d[int((N-1)/2)]

print(result)


### FIXED CODE ###

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

d.sort()
result = d[int(N/2)]-d[int((N-1)/2)]
print(result)
from fractions import gcd
n = int(input())
li = list(map(int, input().split()))
lil = [0]*n
lir = [0]*n
for k in range(n):
  if k == 0:
    lil[k] = li[0]
    lir[k] = li[-1]
  else:
    lil[k] = gcd(lil[k-1], li[k])
    lir[k] = gcd(lir[k-1], li[-k-1])
    
lir = lir[::-1]
tmp = max(gcd(lil[j-1], lir[j+1]) for j in range(1, n-1))
print(max(tmp, lir[1], lil[-2]))

### FIXED CODE ###

A, B, T = map(int, input().split())
print(int(T / A) * B)
N=input()
S=input()
K=int(input())
W=S[K-1]
for i in range(N):
  print(i)
  if S[i]!=W:
    S=S.replace(S[i],'*')
print(S)

### FIXED CODE ###

N=int(input())
S=str(input())
K=int(input())
W=S[K-1]
for i in range(N):
  if S[i]!=W:
    S=S.replace(S[i],'*')
print(S)
import decimal
a, b = map(decimal, input().split())
b = b*1000
c = a*b
print(int(c/1000))

### FIXED CODE ###

a,b = input().split()
a = int(a)
b = int(b.replace(".",""))
print(a*b//100)
# cook your dish here
n,m = map(int,input().split())

par = [[] for i in range(n)]
op = [[]for i in range(n)]
for i in range(n+m-1):
    x,y = map(int,input().split())
    x-=1
    y-=1
    par[y].append(x)
    op[x].append(y)

res = [-1]*n
x = -1
print(par)
print(op)

for i in range(n):
    if len(par[i])==0:
        res[i] = 0
        x = i
        break


used = [0]*n
used[x]=1
def g(y):
    if len(par[y])==0:
        return True
    for pe in par[y]:
        if used[pe]==0:
            return False
    return True
    
#xの下のusedとresを埋める
def f(z):
    if len(op[z])>=1:
        for e in op[z]:
            if used[e]==0 and g(e):
                used[e]=1
                res[e]=z+1
                f(e)
f(x)
for i in range(n):
    print(res[i])


### FIXED CODE ###

from collections import deque

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

up = [[] for i in range(n)]
down= [[]for i in range(n)]
for i in range(n+m-1):
    a,b = map(int,input().split())
    a -=1
    b -=1
    up[b].append(a)
    down[a].append(b)

res = [-1]*n
root = -1

for i in range(n):
    if len(up[i])==0:
        res[i] = 0
        root = i
        break

#0なら不使用
used = [0]*n
used[root]=1

#yの親に不使用が一つも存在しなければTrue
def g(y):
    for pe in up[y]:
        if used[pe]==0:
            return False
    return True
    
#zの下のusedとresを埋める
def f(z):
    for e in down[z]:
        if used[e]==0 and g(e):
            res[e]=z+1
            tank2.append(e)
            usedtank.append(e)
c = 1
tank = deque([root])
tank2 = deque([root])
usedtank = []
while c != n:
    tank = tank2
    tank2 = deque([])
    usedtank = []
    while len(tank)!=0:
        f(tank.popleft())
    for usede in usedtank:
        used[usede]=1
    c += len(tank2)
    
for i in range(n):
    print(res[i])
x,y=map(int, input().split())
mod=10**9+7

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print('0')
else:
    a=(2*y-x)//3
    b=(2*x-y)//3
    n=a+1
    r=b
    ans=comb(n+r-1,r,mod)
    print(int(ans%mod))x,y=map(int, input().split())
mod=10**9+7

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

if (2*y-x)%3!=0 or (2*x-y)%3!=0:
    print('0')
else:
    a=round((2*y-x)/3)
    b=round((2*x-y)/3)
    n=a+1
    r=b
    ans=comb(n+r-1,r,mod)
    print(int(ans%mod))

### FIXED CODE ###

x,y=map(int, input().split())
mod=10**9+7

def framod(n, mod, a=1):
    for i in range(1,n+1):
        a=a * i % mod
    return a

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

if (2*y-x)%3!=0 or (2*x-y)%3!=0 or y>2*x or x>2*y:
    print('0')
else:
    a=round((2*y-x)/3)
    b=round((2*x-y)/3)
    n=a+1
    r=b
    ans=comb(n+r-1,r,mod)
    print(int(ans%mod))
n = int(input())
h = list(map(int,input().split()))
c =0

for i in range(n-1):
    if (h[i+1]-h[i] <= 1) and (h[i+2] >= h[i]):
        c += 1
    else:
        pass
if c == 1:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
c = 0

for i in range(n-1):
    if h[i] <= h[i+1]-1:
        h[i+1] = h[i+1]-1
    elif h[i] == h[i+1]:
        continue
    else:
        c = 1
if c == 1:
    print('No')
else:
    print('Yes')
a, b, c = [int(3) for 3 in input().split() ]

mylist = [5, 7]

if ( a in mylist and b in mylist and c in mylist and a + b + c == 17 ):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

N = 3

a, b, c = [int(N) for N in input().split() ]

d = 17

mylist = [5, 7]

if ( a in mylist and b in mylist and c in mylist and a + b + c == 17 ):
    print("YES")
else:
    print("NO")
a,b,c = input().split()
re = a[0].upper() + b[0].upper() + c[0].upper()
print re

### FIXED CODE ###

strs = raw_input()
strs = strs.split()
print strs[0][0].upper() + strs[1][0].upper() + strs[2][0].upper()
import numpy as np
import math
while True:
    n= int(input())
    if n == 0:
        break
    a=list(map(int,input().split()))
    m=np.mean(a)
    s=0
    for i in a:
        s+=(i-m)**2
    s/=n
    print(math.sqrt(s)) 

### FIXED CODE ###

while True:
    n = int( input() )
    if n==0:
        break
    a=list(map(int, input().split()))
    m=sum(a)/n
    s=0
    for i in a:
        s+=(i-m)**2
    print( ( s/n)**0.5 )
N = int(input())

x = [0] * N
u = [0] * N

for i in range(N):
    x[i], u[i]  = map(int, input().split())


ans = []

btc_1 = 380000.0

for i  in range(N):
    if u[i] == "JPY":
        ans.append(x[i])
    else:
        yen = ((x[i])*(btc_1))
        ans.append(yen)

print(sum(ans))

### FIXED CODE ###

N=int(input())
ans=0
for i in range(N):
    x,u=map(str,input().split())
    x=float(x)
    if u=="JPY":
        ans+=x
    else:
        ans+=380000.0*x
print(ans)
import re

s = ainpu()
s = re.sub("eraser","",s)
s = re.sub("erase","",s)
s = re.sub("dreamer","",s)
s = re.sub("dream","",s)
print("Yes" if len(s) ==0 else "No")

### FIXED CODE ###

import re

s = input()
s = re.sub("eraser","",s)
s = re.sub("erase","",s)
s = re.sub("dreamer","",s)
s = re.sub("dream","",s)

if len(s) == 0:
  print("YES")
else:
  print("NO")
N=input()
d=[input() for i in range(N)]
print(len(set(d)))

### FIXED CODE ###

N=int(input())
d=[input() for i in range(N)]
print(len(set(d)))
numpy as np
a, b, c = map(np.sqrt, map(lambda x:100*x, map(int, input().split())))
print('Yes' if a + b - c < 0  else 'No')


### FIXED CODE ###

a, b, c = map(int, input().split())
print('Yes' if (c-a-b)>0 and 4*a*b < (c - a- b)**2 else 'No')
W, H, x, y = map(int, input().split())
ans = 0
me_x = 0
me_y = 0
total = W * H
# (W - x) * H
if (W - x) > x:
  me_x = x * H
else:
  me_x = (W - x) * H

if (H - y) > y:
  me_y = y * W
else:
  me_y = (H - y) * W

if me_x > me_y:
  me_ans = me_x
else:
  me_ans = me_y

if me_x == (total - me_y):
  ans = 1
elif me_y == (total - me_x):
  ans = 1

if me_x == me_y:
  ans = 1
print(me_ans, ans)

### FIXED CODE ###

X, A = map(int, input().split())
if X < A:
  print(0)
else:
  print(10)
n,a,b = [int(x) for x in input().split()]

s = "b" * a + "r" * b

ans = (n // (a+b)) * a
ama = n % (a+b)

if a <= ama:
    print(ans + s[:ama].count("b"))
else:
    print(ans + ama)

### FIXED CODE ###

n,a,b = [int(x) for x in input().split()]

ans = (n // (a+b)) * a
ama = n % (a+b)

if a <= ama:
    print(ans + a)
else:
    print(ans + ama)
n = int(input())
d,x = map(int,input().split())
count += x
a = []
for i in range(n):
  b = int(input())
  a.append(b)
  for j in range(n):
    if 1 + a[i]*j <= n:
      count += 1
print(count)

### FIXED CODE ###

n = int(input())
m, k = [int(_) for _ in input().split()]
    
for i in range(n):
    for j in range(1, m+1, int(input())):
        k += 1
print(k)
b, c, _ = map(int, raw_input().split())
print(b * c / 2)

### FIXED CODE ###

b, c, _ = map(int, input().split())
print(int(b * c / 2))
N = int(input())
N%=10
if N == 3:
    print("bon")
elif N == 0 or N == 1 or N == 6 N == 8:
    print("pon")
else:
    print("hon")

### FIXED CODE ###

N = int(input())
N%=10
if N == 3:
    print("bon")
elif N == 0 or N == 1 or N == 6 or N == 8:
    print("pon")
else:
    print("hon")
N = int(input())
print((N+1)/2N if N%2 != 0 else 0.5 )

### FIXED CODE ###

N = int(input())
print(((N//2)+1)/N if N%2 != 0 else "0.5" )
n=int(input())
P=list(map(int,input().split()))

ans=0
if P[0]==1:
  P[0]=P[1]
  P[1]=1
  ans+=1
for i in range(1,n):
  if P[i]==i+1:
    if P[i+1]!=i+2:
      P[i]=P[i+1]
      P[i+1]=i+1
    else:
      P[i]=P[i-1]
      P[i-1]=i+1
    ans+=1
print(ans)

### FIXED CODE ###

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

ans=0
for i in range(n-1):
  if P[i]==i+1:
    P[i],P[i+1]=P[i+1],P[i]
    ans+=1
if P[-1]==n:
  ans+=1
print(ans)
import math
from functools import reduce

def main():
    N,X = (int(i) for i in input().split())
    x=list(map(int,input().split()))

    gcd_l = []
    gcd_l.append(abs(X-x[0]))

    for i in range(1,N):
        gcd_l.append(abs(x[i-1]-x[i]))

    print(reduce(math.gcd,gcd_l))

main()

### FIXED CODE ###

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

def main():
    N,X = (int(i) for i in input().split())
    x=list(map(int,input().split()))

    gcd_l = []
    #gcd_l.append(abs(X-x[0]))

    for i in range(0,N):
        gcd_l.append(abs(X-x[i]))
    if N==1:
        ans = gcd_l[0]
    else:
        a = [gcd_l[0],gcd_l[1]]
        ans = gcd(max(a),min(a))
        for n in range(2,len(gcd_l)):
            a = [ans,gcd_l[n]]
            ans = gcd(max(a),min(a))
    print(ans)

main()
N, X = list(map(int, input().split()))
L = list(map(int, input().split()))

d = 0
i = 0
while d <= X:
    d += L[i]
    i += 1
print(i)

### FIXED CODE ###

N, X = list(map(int, input().split()))
L = list(map(int, input().split()))

# while d <= X:
#     if i >= i_max:
#         break
#     d += L[i]
#     i += 1
count = 1
total = 0
for i in range(len(L)):
    total += L[i]
    if total <= X:
        count += 1
print(count)
num = list(map(int,input().split()))
if num[1] > num[2]:
  a = num[2]
else:
  a = num[1]
b = num[1] + num[2] - num[0]
print(a + " " + b)

### FIXED CODE ###

num = list(map(int,input().split()))
if num[1] > num[2]:
  a = num[2]
else:
  a = num[1]
b = num[1] + num[2] - num[0]
if b < 0:
  b = 0
print(str(a) + " " + str(b))
n=int(input())
p=list(map(int,input().split()))
cnt=0
for i in range(n):
  if p[i]==i+1:
    p[i], p[i+1]=p[i+1],p[i]
    cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
cnt=0
for i in range(n-1):
  if p[i]==i+1:
    p[i], p[i+1]=p[i+1],p[i]
    cnt+=1

if p[-1]==n:
  cnt+=1
print(cnt)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import sys
from functools import lru_cache

N = int(input())
INF = 10**18
nums = list(map(int, input().split()))
@lru_cache(None)
def dp(idx, n):
    if idx >= N:
        return -INF
    if N - idx + 2 < 2 * n:
        return -INF
    if n == 0:
        return 0
    elif n == 1:
        return max(nums[idx:])
    return max(nums[idx] + dp(idx + 2, n - 1), dp(idx + 1, n))
print(dp(0, N // 2))


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
##################################
# University of Wisconsin-Madison
# Author: Yaqi Zhang
##################################

# standard library
import sys
sys.setrecursionlimit(10**9)

from functools import lru_cache

def main():
    N = int(input())
    INF = 10**18
    nums = list(map(int, input().split()))
    @lru_cache(None)
    def dp(idx, n):
        if idx >= N:
            return -INF
        if N - idx + 2 < 2 * n:
            return -INF
        if n == 0:
            return 0
        elif n == 1:
            return max(nums[idx:])
        return max(nums[idx] + dp(idx + 2, n - 1), dp(idx + 1, n))
    print(dp(0, N // 2))


if __name__ == "__main__":
    main()