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

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)

def solve(n,ar,k,dp,x):
	ab = abs; s = solve
	if x>=n-2: return dp[x]
	if dp[x] + 1: return dp[x]
	m = 1e9
	for i in range(x+1,n if x+k+1>n else x+k+1):
		t = ab(ar[x]-ar[i])+s(n,ar,k,dp,i)
		m = t if t<m else m
	dp[x] = m	#n([*map(lambda i:ab(ar[x]-ar[i])+solve(n,ar,k,dp,i), range(x+1,mn(n,x+k+1)))])
	return dp[x]

def main():
	(n,k), ar = [[*map(int,s.split())] for s in [*open(0)]]
	dp = [-1]*(n-2)
	dp.append(abs(ar[-2]-ar[-1]))
	dp.append(0)
	pr(solve(n,ar,k,dp,0))

main()

### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

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

# i番目の期待値は(1/p_i)*(sum(1からp_iまでの和)))

def get_E(x):
    return (sum(list(range(1,x+1))))/x

E_list = [get_E(p_i) for p_i in p]


ans = -1
for i in range(n-k+1):
    t = sum(E_list[i:i+k])
    ans = max(ans, t)

print(ans)

### FIXED CODE ###

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

Es = [(1+p_i)/2 for p_i in p]

t = sum(Es[0:k])
ans = t

for i in range(n-k):
    t -= Es[i]
    t += Es[i+k]
    ans = max(ans,t)

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

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

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

ans = 1
for a in A:
    ans *= a

if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 1
for a in A:
    ans *= a
    if ans>10**18:
        print(-1)
        exit()

if ans>10**18:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

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

INF = float('inf')
# dp[n][m] represents total time took to read top n book from A and top m book from B
dp = [[INF] * (M+1) for _ in range(N+1)]
dp[0][0] = 0

count = 0
for i in range(N):
    dp[i+1][0] = dp[i][0] + A[i]
    if dp[i+1][0] > K:
        break
    else:
        count = max(count, i+1)

for i in range(N+1):
    for j in range(M):
        dp[i][j+1] = dp[i][j] + B[j]
        if dp[i][j+1] > K:
            break
        else:
            count = max(i + j + 1, count)

print(count)

### FIXED CODE ###

#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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

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

a = [0]
b = [0]
for i in range(N):
    a.append(a[i] + A[i])

for i in range(M):
    b.append(b[i] + B[i])


count = 0
j = M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    count = max(count, i+j)

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

s=input()
t=s.replace('x','')
if t!=t[::-1] and len(t)!=1:
  print(-1)
  exit()
c=0
while True:
  if s==s[::-1]:
    print(c)
    exit()
  for i in range(len(s)//2):
    if s[i]=='x'and s[len(s)-i-1]!='x':
      s=s[:len(s)-i]+'x'+s[len(s)-i:]
      break
  else:
    for i in range(len(s)//2,len(s)):
      if s[i]=='x'and s[len(s)-i-1]!='x':
        s=s[:len(s)-i-1]+'x'+s[len(s)-i-1:]
        break
  c+=1

### FIXED CODE ###

s=input()
c=0
while len(s)>1:
  if s[0]==s[len(s)-1]:
    s=s[1:len(s)-1]
  elif s[0]=='x':
    c+=1
    s=s[1:]
  elif s[len(s)-1]=='x':
    c+=1
    s=s[:len(s)-1]
  else:
    print(-1)
    exit()
print(c)
### BUGGY CODE ###

n, m = map(int, input().split())
dat_m = [[]] * (n+1)
for i in range(m):
    a,b = map(int, input().split())
    dat_m[a] = dat_m[a] + [b]
# print(dat_m)

c = False
for i in dat_m[1]:
    if n in dat_m[i]:
        c = True
print("POSSIBLE" if c else "IMPOSSIBLE")


### FIXED CODE ###

n, m = map(int, input().split())
dat = []
dat_m = [[]] * (n+1)
dat_finish = [False] * (n+1)

for i in range(m):
    a,b = map(int, input().split())
    dat.append( (a,b) )

#print(dat)
for i in range(m):
    a,b = dat[i]
    if b == n:
        dat_finish[a] = True
#print(dat_finish)

c = False
for i in range(m):
    a,b = dat[i]
    if a == 1:
        if dat_finish[b]:
            c = True

print("POSSIBLE" if c else "IMPOSSIBLE")
### BUGGY CODE ###

from operator import itemgetter

n = int(input())
a = [input() for i in range(n)]
b = list(set(a))
b.sort()
c = []

max = a.count(b[0])

for i in range(len(b)):
	c.append(a.count(b[i]))

unique_count = list(zip(b, c))
unique_count.sort(key = itemgetter(1), reverse=True)

for j in range(len(unique_count)):
	if unique_count[j][1] == unique_count[0][1]:
		print(unique_count[j][0])

### FIXED CODE ###

import collections

n = int(input())
a = [input() for i in range(n)]
c = collections.Counter(a)

i = 0

common = c.most_common()
common.sort(key = lambda x: x[1], reverse=True)

ans = []

while common[i][1] >= common[0][1]:
	ans.append(common[i][0])

	if i < len(common)-1:
		i += 1
	else:
		break

ans.sort()

for i in range(len(ans)):
	print(ans[i])
### BUGGY CODE ###

# 制約条件
MAX_RESULT = 1000000000000000000

N = int(input())
A1 = [int(x) for x in input().split()]

tmp = 1

for x in range(len(A1)):
    tmp = tmp * A1[x]

result = tmp

if (result > MAX_RESULT):
    result = -1

print(result)

### FIXED CODE ###

def main():
    # 制約条件
    MAX_RESULT = 1000000000000000000
    
    N = int(input())
    A = [int(x) for x in input().split()]
    
    if 0 in A:
        result = 0
        print(result)
        return
    
    result = 1
    
    for x in A:
        result *= x
        if result > MAX_RESULT:
            print(-1)
            return
    print(result)
main()
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a=[i for i in a if not i==min(a)]
if len(a)%(k-1)==0:
    print(len(a)//(k-1))
else:
    print(len(a)//(k-1)+1)

### FIXED CODE ###

from collections import Counter
n,k=map(int,input().split())
a=list(map(int,input().split()))
tmp=min(a)
count_min=Counter(a)[tmp]
kazu=n-count_min
if kazu%(k-1)==0:
    print(kazu//(k-1))
else:
    print(kazu//(k-1)+1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  dp2=[]
  for i in range(N+1):
    x=[]
    for j in range(W+1):
      x.append([])
    dp2.append(x)
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
          x=copy.copy(dp2[i][w-weight[i]])
          x.append(i)
          dp2[i+1][w]=x
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=dp2[i][w]
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=dp2[i][w]
  return [dp[N][W],dp2[N][W]]
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
x=z[0];y=z[1]
L=[0 for i in range(n)]
m=0
for i in range(len(y)):
  L[y[i]]=1
M=[]
for i in range(n):
  if L[i]==0:
    M.append(b[i])
if len(M)==0:
  print(x)
else:
  print(x+max(M))

### FIXED CODE ###

import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t-i])
print(max(ans))
### BUGGY CODE ###

from collections import deque

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

cnt = [[10 ** 10] * w for _ in range(h)]
queue = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            cnt[i][j] = 0
            queue.append([i, j])

def bfs(q, c):
    while q:
        y, x = q.pop()
        for i, j in ([0, 1], [1, 0], [-1, 0], [0, -1]):
            ny = y + i
            nx = x + j
            if 0 <= nx < w and 0 <= ny < h and c[ny][nx] >= c[y][x] + 1:
                c[ny][nx] = c[y][x] + 1
                q.append([ny, nx])
    



bfs(queue, cnt)

ans = 0
for i in range(h):
    ans = max(ans, max(cnt[i]))
print(ans)

### FIXED CODE ###

from collections import deque

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

cnt = [[10 ** 10] * w for _ in range(h)]
visited = [[0] * w for _ in range(h)]
queue = deque()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            cnt[i][j] = 0
            queue.append([i, j])
            visited[i][j] = 1

def bfs(q, v, c):
    while q:
        y, x = q.popleft()
        for i, j in ([0, 1], [1, 0], [-1, 0], [0, -1]):
            ny = y + i
            nx = x + j
            if 0 <= nx < w and 0 <= ny < h and v[ny][nx] == 0:
                c[ny][nx] = c[y][x] + 1
                v[ny][nx] = 1
                q.append([ny, nx])

bfs(queue, visited, cnt)

ans = 0
for i in range(h):
    ans = max(ans, max(cnt[i]))
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]
a.sort()
aSum = 0
cnt = 0
for i in range(n):
    aCnt = a.count(a[cnt])
    if aCnt % 2 == 1:
        aSum += 1
    cnt += aCnt
    if cnt >= n:
        break


print(aSum)


### FIXED CODE ###

import sys
import collections
import bisect


def main():
    n = int(input())
    A = [int(input()) for _ in range(n)]
    c = collections.Counter(A)
    sumA = 0
    cKeys = c.keys()
    for cKey in cKeys:
        sumA += c[cKey] % 2
    print(sumA)


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

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

res = 0

for i in range(len(A)):
  a = A[i]
  nokori = A[i+1:]
  for j in nokori:
    res += (a * j) % (10 ** 9 + 7)
print(res % (10 ** 9 + 7))

### FIXED CODE ###

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

res = 0
sums = sum(A)
for i in range(len(A)):
  sums = sums - A[i]
  a = A[i]
  res += ((a * sums) % (10 ** 9 + 7))
print(res % (10 ** 9 + 7))
### BUGGY CODE ###

from collections import deque
import numpy as np
h, w = map(int, input().split())
mass = [list(input()) for _ in range(h)]

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(s, t):
    if mass[s][t] == "#":
        return 0
    visited = np.zeros((h, w))
    depth = np.zeros((h, w))
    q1 = deque([s])
    q2 = deque([t])
    while q1:
        x = q1.popleft()
        y = q2.popleft()
        visited[x][y] += 1
        r = depth[x][y] + 1
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            if nx < 0 or h - 1 < nx:
                continue
            if ny < 0 or w - 1 < ny:
                continue

            if mass[nx][ny] == "#":
                continue
            if visited[nx][ny]:
                continue

            q1.append(nx)
            q2.append(ny)
            depth[nx][ny] = r
    return np.max(depth)


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, bfs(i, j))
print(int(ans))



### FIXED CODE ###

import numpy as np
from collections import deque
h, w = map(int, input().split())
r = [list(input()) for i in range(h)]


def dist(s, t):
    if r[s][t] == "#":
        return 0
    else:
        visited = np.zeros((h, w))
        visited[s][t] += 1
        distance = np.zeros((h, w))
        q = deque([[s, t]])
        while len(q) > 0:
            i, j = q.popleft()
            d = distance[i][j] + 1
            if j != w-1:
                if r[i][j+1] == "." and not visited[i][j+1]:
                    q.append([i, j + 1])
                    visited[i][j+1] += 1
                    distance[i][j+1] += d
            if j != 0:
                if r[i][j-1] == "." and not visited[i][j-1]:
                    q.append([i, j - 1])
                    visited[i][j - 1] += 1
                    distance[i][j - 1] += d
            if i != 0:
                if r[i-1][j] == "." and not visited[i-1][j]:
                    q.append([i - 1, j])
                    visited[i-1][j] += 1
                    distance[i-1][j] += d
            if i != h-1:
                if r[i+1][j] == "." and not visited[i+1][j]:
                    q.append([i + 1, j])
                    visited[i+1][j] += 1
                    distance[i+1][j] += d
        return np.max(distance)


ans = 0
for s in range(h):
    for t in range(w):
        ans = max(ans, dist(s, t))

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

#coding:utf-8
import sys
from fractions import gcd
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True

def index(a,b):
    return str(min(a,b)) + "," +  str(max(a, b))

def main(given = sys.stdin.readline):
    input = sys.stdin.readline

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

    koubaisu = 1
    for i in a:
        koubaisu = koubaisu * (i // 2) // gcd(koubaisu, i//2)

    for i in a:
        if koubaisu // (i//2) % 2 == 0:
            print(0)
            exit()

    print(M // koubaisu - M // (2*koubaisu))




if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from fractions import gcd

def solve(N: int, M: int, a: "List[int]"):
    koubaisu = a[0]
    for i in range(1, N):

        koubaisu = koubaisu * a[i] // gcd(koubaisu, a[i])

    for i in a:
        if koubaisu // i % 2 == 0:
            print(0)
            exit()

    print(M // koubaisu - M // (2*koubaisu))


    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int(next(tokens)) // 2 for _ in range(N)]  # type: "List[int]"
    solve(N, M, a)

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

N, K = map(int, input().split())
XY = [tuple(map(int, input().split())) for _ in range(N)]

ans = 10 ** 20

for x1 in range(N):
    for x2 in range(x1 + 1, N):
        for y1 in range(N):
            for y2 in range(y1 + 1, N):
                u = max(XY[x1][0], XY[x2][0])
                d = min(XY[x1][0], XY[x2][0])
                r = max(XY[y1][1], XY[y2][1])
                l = min(XY[y1][1], XY[y2][1])
                c = sum([d <= x <= u and l <= y <= r for x, y in XY])
                ans = min(ans, (u - d) * (r - l)) if c >= K else ans

print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
XY = sorted([tuple(map(int, input().split())) for _ in range(N)])

ans = 10 ** 20
for xl in range(N):
    for xr in range(xl + 1, N):
        Ysub = sorted([y for x, y in XY[xl:xr + 1]])
        for i in range(xr - xl - K + 2):
            Yk = Ysub[i:i + K] + [XY[xr][1], XY[xl][1]]
            ans = min(ans, (XY[xr][0] - XY[xl][0]) * (max(Yk) - min(Yk)))

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

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

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

# i番目までからj個選んで和をkにできる選び方の総数
# 選ばない状態も持ちたいから配列は1まわり大きく
dp = [[[0 for k in range(n*a+1)] for j in range(n+1)] for i in range(n+1)]

for i in range(n+1):
    for j in range(n+1):
        for k in range(n*a+1):
            # 初期条件
            if i == 0 and j == 0 and k == 0:
                dp[i][j][k] = 1

            # x_iが和を超過してしまう場合
            elif i > 0 and k < X[i-1]:
                dp[i][j][k] = dp[i-1][j][k]

            # 和を作れる場合
            # 加算する場合としない場合の両方を考える
            elif i > 0 and j > 0 and k >= X[i-1]:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

            # その他
            else:
                dp[i][j][k] = 0

# i枚選んだ時の合計がiAであればよい
ans = 0
for i in range(1, n+1):
    ans += dp[n][i][i*a]

print(ans)


### FIXED CODE ###

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

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

# i番目までからj個選んで和をkにできる選び方の総数
# 選ばない状態も持ちたいから配列は1まわり大きく
dp = [[[0 for k in range(n*a+1)] for j in range(n+1)] for i in range(n+1)]

for i in range(n+1):
    for j in range(n+1):
        for k in range(n*a+1):
            # 初期条件
            if i == 0 and j == 0 and k == 0:
                dp[i][j][k] = 1

            # x_iが和を超過してしまう場合
            elif i > 0 and k < X[i-1]:
                dp[i][j][k] = dp[i-1][j][k]

            # 和を作れる場合
            # 加算する場合としない場合の両方を考える
            elif i > 0 and j > 0 and k >= X[i-1]:
                dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k-X[i-1]]

            # その他
            else:
                dp[i][j][k] = 0

# i枚選んだ時の合計がiAであればよい
ans = 0
for i in range(1, n+1):
    ans += dp[n][i][i*a]

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

from itertools import accumulate
n,k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(k):
    imos = [0] * (n+1)
    for i,a in enumerate(As):
        l = max(0, i-a)
        r = min(n, i+a+1)
        imos[l] += 1
        imos[r] -= 1
    acc = list(accumulate(imos))
    # 指数関数的に増えるので、capする
    if acc[:-1] == As:
        print(*As)
        exit()
    As = acc[:-1]
print(*As)

### FIXED CODE ###

from itertools import accumulate
n,k = map(int, input().split())
As = list(map(int, input().split()))
for i in range(k):
    imos = [0] * (n+1)
    for i,a in enumerate(As):
        l = max(0, i-a)
        r = min(n, i+a+1)
        imos[l] += 1
        imos[r] -= 1
    acc = list(accumulate(imos))
    # 指数関数的に増える
    if acc[:-1] == As:
        print(*As)
        exit()
    As = acc[:-1]
print(*As)
### BUGGY CODE ###

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

ACpos = []
i = 0
while(i < N - 1):
    if("AC" == S[i:i+2]):
        ACpos.append(i + 1)
        i += 1
    i += 1
#print("ACpos = {}".format(ACpos))

for idx in lr:
    cnt = 0
    for pos in ACpos:
        if((idx[0] <= pos) & (pos < idx[1])):
            cnt += 1
#    print("cnt = {}, idx = {}".format(cnt, idx))
    print(str(cnt))


### FIXED CODE ###

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

ACnum = [0]
for i in range(N - 1):
    ACnum.append(ACnum[-1])
    if("AC" == S[i:i + 2]):
        ACnum[i + 1] += 1
#print("ACnum = {}".format(ACnum))

for l, r in lr:
    print(str(ACnum[r - 1] - ACnum[l - 1]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

ans = 0

for i in range(0, len(P)-1):
    if (P[1] <= P[0]):
        ans += 1
        del(P[0])
    else:
        del(P[1])

print(ans+1)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ans = 0
pivot = P[0]

for i in range(0, len(P)):
    if (pivot >= P[i]):
        ans += 1
        pivot = P[i]

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

def check(A):
	c = 0
	for i in range(H):
		for j in range(W):
			if A[i][j] == ".":
				return 1
	return 0

def change(A):
	for i in range(H):
		for j in range(W):
			if A[i][j] == "?":
				A[i][j] = "#"
	return A

H,W = map(int,input().split())
A = []
for i in range(H):
	A.append([s for s in input()])

c = 0
while check(A) != 0:
	for i in range(H):
		for j in range(W):
			if A[i][j] == "#":
				if i != 0:
					if A[i-1][j] != "#":
						A[i-1][j] = "?"
				if i != H-1:
					if A[i+1][j] != "#":
						A[i+1][j] = "?"
				if j != 0:
					if A[i][j-1] != "#":
						A[i][j-1] = "?"
				if j != W-1:
					if A[i][j+1] != "#":
						A[i][j+1] = "?"
	A = change(A)
	c += 1
print(c)

### FIXED CODE ###

import numpy as np

H,W = map(int,input().split())
A = []
for i in range(H):
	A.append([0 if s == "#" else H+W for s in input()])

A = np.array(A)
for x in range(W - 1):
	A[:,x+1] = np.minimum(A[:, x]+1,A[:, x+1])
for x in range(W - 1, 0 , -1):
	A[:,x-1] = np.minimum(A[:, x-1],A[:, x]+1)
for y in range(H -1):
	A[y+1,:] = np.minimum(A[y, :]+1,A[y+1, :])
for y in range(H -1, 0, -1):
	A[y-1,:] = np.minimum(A[y-1, :],A[y, :]+1)

print(np.max(A))
### BUGGY CODE ###

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

benefits = [max([a[j] - a[i] for j in range(i, n)]) for i in range(n)]

print(benefits.count(max(benefits)))

### FIXED CODE ###

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

max_benefit = 0
a_min = a[0]
ans = 0
for i in range(1, n):
    if a[i] < a_min:
        a_min = a[i]
    benefit = (a[i] - a_min)
    if  benefit == max_benefit:
        ans += 1
    elif benefit > max_benefit:
        ans = 1
        max_benefit = benefit

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

a,b,k=map(int,input().split())
l=[]
for i in range(a,b+1):
    l.append(i)
if 2*k>len(l):
    for i in range(len(l)):
        print(l[i])
else:
    for i in range(k):
        print(l[i])
    for i in range(k):
        print(l[-k+i])

### FIXED CODE ###

a,b,k=map(int,input().split())
if 2*k>b-a+1:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(k):
        print(a+i)
    for i in range(k):
        print(b-k+1+i)
### BUGGY CODE ###

def get_item(L,i): return L[i] if len(L) > i else -2
def left(i): return i*2 + 1
def right(i): return (i+1)*2
def parent(i): return i//2 if i%2 == 1 else i//2 - 1

def dw_heap(A,i):
    l = left(i)
    r = right(i)
    largest = i
    if get_item(A,l) > A[largest]: largest = l
    if get_item(A,r) > A[largest]: largest = r
    if largest != i:
        A[i], A[largest] = A[largest], A[i] 
        dw_heap(A, largest)


def up_heap(A,i):
    if i==0: return
    p = parent(i)
    if A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        up_heap(A,p)


def insert(A,k):
    A.append(k)
    up_heap(A,len(A)-1)


def extract(A):
    A[0],A[-1] = A[-1],A[0]
    max_item = A.pop()
    dw_heap(A,0)
    return max_item


if __name__=='__main__':
    hp = []
    while True:
        op = input().split() 
        if   op[0] == 'end': break
        if   op[0] == 'insert': insert(hp,int(op[1]))
        else: print(extract(hp))

### FIXED CODE ###

from sys import stdin

def dw_heap(A,i):
    largest = i
    while True:
        l = i*2
        r = l + 1
        if A[l] > A[largest]: largest = l
        if A[r] > A[largest]: largest = r
        if largest == i: return
        A[i], A[largest] = A[largest], A[i] 
        i = largest

def up_heap(A,i):
    p = i//2
    while A[i] > A[p]:
        A[i], A[p] = A[p], A[i] 
        i = p
        p = i//2

if __name__=='__main__':
    hp = [-1]*(4000000)
    hp[0] = 2000000001
    i = 1
    j = -1 
    for op in stdin:
        if op[0] == 'i':# insert
            hp[i] = int(op[7:])
            up_heap(hp,i)
            i += 1
        elif op[1] == 'x':# extract
            hp[j],hp[1],hp[i-1] = hp[1],hp[i-1],-1
            dw_heap(hp,1)
            i -= 1
            j -= 1
        else:# end
            break
    print(*hp[:j:-1],sep='\n')