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

N = int(input())
A = list(map(int, input().split())) 
klists = []
B = [A[0]]
for i in range(N-1):
    if max(B) > A[i+1]:
        k = max(B)-A[i+1]
        klists.append(k)
        A[i+1] = A[i+1] + k
    B.append(A[i+1])
        
print(sum(klists))



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split())) 
klists = []
B = [A[0]]
for i in range(N-1):
    if B[i] > A[i+1]:
        k = B[i]-A[i+1]
        klists.append(k)
        A[i+1] = A[i+1] + k
    B.append(A[i+1])
        
print(sum(klists))
### BUGGY CODE ###

import sys
from operator import itemgetter


scan = sys.stdin.readline


def main():
  n, m = map(int, scan().rstrip().split())
  a = list(map(int, scan().rstrip().split()))
  operations = [tuple(map(int, scan().rstrip().split())) for _ in range(m)]
  
  a.sort()
  operations.sort(key=itemgetter(1), reverse=True)
  
  for b, c in operations:
    count = 0
    while a[count] < c and count < b:
      a.append(c)
      count += 1
    a = a[count:]
  
  print(sum(a))
  

if __name__ == "__main__":
  main()


### FIXED CODE ###

import sys
from operator import itemgetter
from collections import deque


scan = sys.stdin.readline


def main():
  n, m = map(int, scan().rstrip().split())
  a = list(map(int, scan().rstrip().split()))
  operations = [tuple(map(int, scan().rstrip().split())) for _ in range(m)]
  
  a.sort()
  operations.sort(key=itemgetter(1), reverse=True)
  
  a = deque(a)
  
  for b, c in operations:
    count = 0
    while count < b:
      if a[0] < c:
        a.append(c)
        count += 1
        a.popleft()
      else:
        print(sum(a))
        exit(0)

  print(sum(a))
  

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

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

pair = 0
for i in range(N):
    for j in range(i, N):
        if (A[i]+A[j])==abs(i-j):
            pair +=1
print (pair)

### FIXED CODE ###

from collections import Counter

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

List1 = [i + A[i] for i in range(N)]
List2 = [i - A[i] for i in range(N)]

ans = 0

CList1 = Counter(List1)
CList2 = Counter(List2)

for i in range(N):
    ans += CList1[i]*CList2[i]
    
print (ans)
### BUGGY CODE ###

n, m = (int(x) for x in input().split())

B = []
A = list(int(x) for x in input().split())

for i in range(m):
    j, k = (int(x) for x in input().split())
    C = [j, k]
    B.append(C)

count = 0

for i in range(1, n + 1):
    D = []
    for l in B:
        if i in l:
            for a in l:
                D.append(a)
        else:
            pass
    if len(D) == 0:
        count += 1
    else:
        b = set(D)
        apple = list(b)
        apple.remove(i)
        E = []
        for cat in apple:
            dog = A[cat - 1]
            E.append(dog)
        if A[i - 1] > max(E):
            count += 1
        else:
            pass
print(count)

### FIXED CODE ###

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


ans = [1] * n
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if hs[a] < hs[b]:
        ans[a] = 0
    elif hs[a] == hs[b]:
        ans[a] = 0
        ans[b] = 0
    else:
        ans[b] = 0

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

n,m=map(int,input().split())
a=[]
k=[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  k.append(sum(2**(int(i)-1)for i in input().split()))
inf=float('inf')
dp=2**n*[inf]
dp[0]=0
for i in range(2**n):
  for j in range(m):
    dp[i|k[j]]=min(dp[i|k[j]],dp[i]+a[j])
print(dp[-1]if inf!=dp[-1]else-1)


### FIXED CODE ###

n,m=map(int,input().split())
a=[]
k=[]
for _ in range(m):
  a.append(list(map(int,input().split()))[0])
  k.append(sum(2**(int(i)-1)for i in input().split()))
inf=float('inf')
dp=2**n*[inf]
dp[0]=0
for i in range(2**n):
  for j in range(m):
    dp[i|k[j]]=min(dp[i|k[j]],dp[i]+a[j])
print(dp[-1]if inf!=dp[-1]else-1)
### BUGGY CODE ###

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

mod = 998244353

S = []
for _ in range (K):
    l,r = map(int,input().split())
    for i in range (l,r+1):
        S.append(i)

S.sort()

ans = [0]*N
ans[0] = 1

for i in range (1,N):
    for j in S:
        if i-j < 0:
            break
        else:
            ans[i] += ans[i-j]
            ans[i] %= mod


print(ans[N-1])


### FIXED CODE ###

def main():
    N, K = map(int,input().split())

    mod = 998244353

    S = []
    for _ in range (K):
        S.append(list(map(int,input().split())))

    S.sort()
    #print(S)

    ans = [0]*N
    acc = [0]*N
    ans[0] = 1
    acc[0] = 1

    for i in range (1,N):
        for l,r in S:

            if i-l < 0:
                break
            else:
                ans[i] += acc[i-l]
            if i-r -1 < 0:
                break
            else:
                ans[i] -= acc[i-r-1]

        ans[i] %= mod
        acc[i] = (acc[i-1]+ans[i])%mod


    print(ans[N-1])


main()
### BUGGY CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	e_colors = [[] for _ in range(N)]
	ans_colors = []
	max_color = 0
	for i in range(N-1):
		a,b = MI()
		a -= 1
		b -= 1
		to[a].append(b)
		to[b].append(a)
		l = max(len(to[a]),len(to[b]))
		ch=np.array([False]*(N-1))
		ch[e_colors[a]]=True
		ch[e_colors[b]]=True
		for j in range(N-1):
			if(ch[j]==False):
				e_colors[a].append(j)
				e_colors[b].append(j)
				ans_colors.append(j)
				if(max_color < j+1):
					max_color = (j+1)
				break
	print(max_color)
	for i in range(N-1):
		print(ans_colors[i]+1)

main()

### FIXED CODE ###

import sys,math

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	N = II()
	to = [[] for _ in range(N)]
	ans = {}
	order = []
	for i in range(N-1):
		a,b = MI()
		a -= 1;b -= 1
		ans[str(a)+"-"+str(b)] = 0
		order.append(str(a)+"-"+str(b))
		to[a].append(b);to[b].append(a)
	
	def bfs():
		from collections import deque
		hist = [True]*N
		que = deque()
		que.append(0)
		e_colors = [0]*N
		max_c = 0
		while len(que) > 0:
			n = que.popleft()
			hist[n]=False
			for i in to[n]:
				if(hist[i]):
					ch = e_colors[n] | e_colors[i]
					index = int(math.log2(~ch & -~ch))
					e_colors[n] += 1 << index
					e_colors[i] += 1 << index
					ans[str(min(n,i))+"-"+str(max(n,i))] = index+1
					if(max_c < index+1): max_c = index+1
					que.append(i)
		print(max_c)
		for i in order:
			print(ans[i])

	bfs()


main()
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())
a.sort()
cnt=[0]*(a[-1]+1)
while a:
  m=a.pop(0)
  cnt[m]+=1
  i=0
  while i<len(a):
    if a[i]%m==0 and a[i]//m>1:
      a.pop(i)
      continue
    i+=1
ans=0
for ci in cnt:
  ans+=(1 if ci==1 else 0)
print(ans)

### FIXED CODE ###

n,*a=map(int,open(0).read().split())
a.sort()
m=a[-1]+1
cnt=[0]*m
for ai in a:
  if cnt[ai]!=0:
    cnt[ai]+=1
    continue
  for i in range(ai,m,ai):
    cnt[i]+=1
ans=0
for ai in a:
  ans+=(cnt[ai]==1)
print(ans)
### BUGGY CODE ###

N = int(input())
A_list = [int(input()) for _ in range(N)]
from collections import deque
queue = deque()
for A in A_list:
    next = -1
    for q in queue:
        if (q < A):
            next += 1
    if (next == -1):
        queue.appendleft(A)
    elif (next == len(queue)):
        queue.append(A)
    else:
        queue[next] = A
print(len(queue))


### FIXED CODE ###

from collections import deque
from bisect import bisect_left
N = int(input())
A = [int(input()) for _ in range(N)]
queue = deque()
for a in A:
    pos = bisect_left(queue, a)
    if (pos == 0):
        queue.appendleft(a)
    else:
        queue[pos-1] = a
print(len(queue))
### BUGGY CODE ###

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n

	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)

		if x==y:
			return
		if self.parents[x] > self.parents[y]:
			x,y=y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x
        
n,m=input2()
AB=[input_array() for _ in range(m)]
D=[[0]*n for _ in range(n)]

uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in range(n):
	tmp=uf.find(i)
	if tmp!=0:
		ans+=1
print(ans)

### FIXED CODE ###

#入力:N,M(int:整数)
def input2():
	return map(int,input().split())

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

class UnionFind():
	"""docstring for UnionFind"""
	def __init__(self, n):
		self.parents = [-1]*n

	def find(self,x):
		if self.parents[x] < 0: #自分が親である時
			return x
		else: #自分が子供である時
			self.parents[x]=self.find(self.parents[x])
			return self.parents[x]

	def union(self,x,y):
		# 各要素の親要素を返す
		x=self.find(x)
		y=self.find(y)

		if x==y:
			return
		if self.parents[x] > self.parents[y]:
			x,y=y,x

		self.parents[x]+=self.parents[y]
		self.parents[y]=x
		# print(self.parents)
n,m=input2()
AB=[input_array() for _ in range(m)]


uf = UnionFind(n)
for ab in AB:
	a=ab[0]
	b=ab[1]
	uf.union(a-1,b-1)

ans=0
for i in uf.parents:
	if i < 0:
		ans+=1
print(ans-1)
### BUGGY CODE ###

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

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

L = []
L.append(1)
f = 1
memo = []
flg = 0
leng = 0

while 1:
    L.append(A[f-1])
    memo.append(f)
    f = A[f-1]
    leng += 1
    for i in range(leng):
        if f == memo[i]:
            loop = leng - i
            flg = 1
            break
    if flg == 1:
        break

#print(L)
#NL = L[0:-1]
#print(NL)
#print(memo)
#print(loop)

#a = K % len(NL)
#print(NL[a])

cycle = memo[-loop:]
#print(cycle)

if K <= len(memo) - loop:
    print(memo[K])
else:
    K -= len(memo) - loop
    a = K % len(cycle)
    print(cycle[a])

### FIXED CODE ###

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

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

L = []
L.append(1)
f = 1
memo = [-1] * N
memo[0] = 0
cnt = 1

while 1:
    L.append(A[f-1])
    f = A[f-1]
    if memo[f-1] != -1:
        loop = cnt - memo[f-1]
        break
    memo[f-1] = cnt
    cnt += 1

#print(L)
#print(loop)
NL = L[-(loop+1):-1]
#print(NL)

if K <= (len(L) - 1) - loop:
    print(L[K])
else:
    K -= (len(L) - 1) - loop
    a = K % len(NL)
    print(NL[a])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = []
for i in range(Q):
    B, C = map(int,input().split())
    while B in A:
        # A = A.replace(B, C)
        A[A.index(B)] = C

    S.append(sum(A))


for s in S:
    print(s)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = []
c = 0
s = sum(A)
table = [0] * 100010
# A = pd.Series(A)
# for a in A:
#     print(a)

for i in A:
    table[i] += 1

for i in range(Q):
    B, C = map(int,input().split())
    # if B in A:
    # c = A.count(B)
    c = table[B]
    s += (C - B) * c
    table[C] += table[B]
    table[B] = 0
    # print(s)
        # print((C - B) * c) 
        # string = ",".join(A)
        # string_new = string.replace(B,C)
        # A =  string_new.split(",")
        # s = sum(map((lambda x: int(x)), A))
    S.append(s)

        # A.replace(B, C,c)
        # while B in A:
        #     A[A.index(B)] = C
    # for a in A:
    #     print(a)
    # else:
        # S.append(s)



for s in S:
    print(s)
### BUGGY CODE ###

def bfs(graph, start, goal):
    visited = {start: None}
    unvisited = [start]
    while unvisited:
        now = unvisited[0]
        if now == goal:
            return "yes"
        unvisited = unvisited[1:]
        for next in graph[now][1:]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return "no"

n, m = map(int, input().split())
g = [[i] for i in range(n)]

for i in range(m):
    inp = list(map(int, input().split()))
    g[inp[0]].append(inp[1])
    g[inp[1]].append(inp[0])

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    print(bfs(g, s, t))

### FIXED CODE ###

from collections import deque

def bfs(graph, start):
    visited = {start: None}
    unvisited = deque()
    unvisited.append(start)
    while unvisited:
        now = unvisited.popleft()
        for next in graph[now]:
            if not (next in visited):
                unvisited.append(next)
                visited[next] = now
    return visited

n, m = map(int, input().split())
g = [set() for i in range(n)]
group = []

for i in range(m):
    a, b = map(int, input().split())
    g[a].add(b)
    g[b].add(a)

q = int(input())

for i in range(q):
    s, t = map(int, input().split())
    for j in range(len(group)):
        if s in group[j] and t in group[j]:
            print("yes")
            break
        elif s in group[j]:
            print("no")
            break
    else:
        group_tmp = set(bfs(g, s).keys())
        if t in group_tmp:
            print("yes")
        else:
            print("no")
        group.append(group_tmp)
### BUGGY CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
ary = [int(stdin.readline().rstrip()) for _ in range(n)]
for i in range(n):
    print(max(max(ary[:i], ary[i+1:])))


### FIXED CODE ###

from sys import stdin
import numpy as np
n = int(stdin.readline().rstrip())
ary = np.array([int(stdin.readline().rstrip()) for _ in range(n)])
m = ary.argmax()
mv = ary.max()
for i in range(n):
    if i == m:
        if i == 0:
            print(np.amax(ary[i + 1:]))
        elif i == n - 1:
            print(np.amax(ary[:i]))
        else:
            print(max(np.amax(ary[:i]), np.amax(ary[i + 1:])))
    else:
        print(mv)
### BUGGY CODE ###

import numpy as np

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

B = A.copy()
discount_cnt = np.zeros(N)

num = 0

while num < M:
    tmp = B / 2
    tmp_idx = np.argmax(tmp)
    discount_cnt[tmp_idx] += 1
    B[tmp_idx] = tmp[tmp_idx]
    num += 1

tmp_arr = np.array([2 ** i for i in discount_cnt])
print(int(np.sum(np.floor(A / tmp_arr))))


### FIXED CODE ###

import heapq


N, M = map(int, input().split())
A = list(map(int, input().split()))
A_inv = [-a for a in A]
heapq.heapify(A_inv)
for _ in range(M):
    max_inv = heapq.heappop(A_inv)
    heapq.heappush(A_inv, -(-max_inv//2))

print(sum([-a for a in A_inv]))
### BUGGY CODE ###

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

max = []
for i in range(N-K+1):
    #print(i)
    target = P[i:i+K]
    #print(target)
    if sum(max) < sum(target):
        max = target

#aprint(max)
ans = (sum(max) + K)/2
print(ans)


### FIXED CODE ###

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

''' 累積和 '''
cumulative_sum = [P[0]]
for i in range(len(P)-1):
    cumulative_sum.append(cumulative_sum[i] + P[i+1])

#入力
#print(P)
#累積和
#print(cumulative_sum)

#numpy 累積和（高速）
#import numpy
#res = numpy.cumsum(P)
#print(res)

''' 最大値探索 O(N-K) '''
#初期値
max = cumulative_sum[K-1]
max_index = 0
for i in range(N-K):
    now = cumulative_sum[K+i] - cumulative_sum[i]
    if max < now:
        max = now
        index = i
#print(max)
#print(max_index)


ans = (max + K)/2
print(ans)
### BUGGY CODE ###

a = input()
a_list = list(map(int, input().split()))
ans = 0
check_set = set(a_list)

for i in check_set:
    ans = max(ans, a_list.count(i-1) + a_list.count(i) + a_list.count(i+1))
  
print(ans)

### FIXED CODE ###

from collections import Counter
a = input()
a_list = list(map(int, input().split()))
ans = 0
b_list = []
c_list = []

for i in a_list:
    b_list.append(i+1)
    c_list.append(i-1)

ans_list = a_list + b_list + c_list
counter = Counter(ans_list)
print(counter.most_common()[0][1])
### BUGGY CODE ###

n,x,y = map(int, input().split())
dst = [[0 for j in range(n)] for i in range(n)]

for i in range(n):
    for j in range(n):
        dst[i][j] = min(abs(i-j), abs(x-1-i)+abs(y-1-j)+1, abs(x-1-j)+abs(y-1-i)+1)

ans = [0]*n
for k in range(n):
    for l in range(n):
        ans[k] += dst[l].count(k)


for m in range(1,n):
    print(ans[m]//2)

### FIXED CODE ###

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

for i in range(n):
    for j in range(1,n-i):
        d = min(j, abs(x-1-i)+abs(y-1-(i+j))+1)
        ans[d-1] += 1

for m in range(n-1):
    print(ans[m])
### BUGGY CODE ###

# coding: utf-8
import math
import bisect
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

def isOK(index,key):
    if l[index] <= key:
        return True
    else:
        return False

def binary_search(key):
    left=len(l)-1
    right=-1
    
    while abs(right - left) >1:
        mid=(right+left)//2
        
        if isOK:
            right=mid
        else:
            left=mid
    return right

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

primes=callIsPrime(10**5)
l=[]

for i in range(len(primes)):
    if (primes[i]+1)//2 in primes:
        l.append(primes[i])
        
Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    L=bisect.bisect_left(l,L)
    R=bisect.bisect_right(l,R)
    
    print(R-L)
    
    


    



### FIXED CODE ###

# coding: utf-8
import math
import bisect
# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2: return False
    # 2は素数
    elif num == 2: return True
    # 偶数は素数ではない
    elif num % 2 == 0: return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num))+1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

def isOK(index,key):
    if l[index] <= key:
        return True
    else:
        return False

def binary_search(key):
    left=len(l)-1
    right=-1
    
    while abs(right - left) >1:
        mid=(right+left)//2
        
        if isOK:
            right=mid
        else:
            left=mid
    return right

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

primes=callIsPrime(10**5)
l=[]

for i in range(len(primes)):
    if (primes[i]+1)//2 in primes:
        l.append(primes[i])
        
Q=int(input())
for i in range(Q):
    L,R=map(int,input().split())
    L=bisect.bisect_left(l,L)
    R=bisect.bisect_right(l,R)
    
    print(R-L)
### BUGGY CODE ###

def main():
    s = input()
    Q = int(input())
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            s = s[::-1]
        else: # q[0]=="2"
            if q[1] == "1":
                s = q[2] + s
            else:
                s += q[2]
    
    print(s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect

def main():
    s = input()
    qc = int(input())
    front = ""
    back = ""
    direct = 1
    for _ in range(qc):
        t = input()
        if t[0] == "1":
            direct = 2 if direct == 1 else 1
        else:
            _,f,c = t.split()
            if f == "1":
                if direct == 1:
                    front += c
                else:
                    back += c
            else:
                if direct == 1:
                    back += c
                else:
                    front += c
    if direct % 2 == 0:
        print((s+back)[::-1] + front)
    else:
        print(front[::-1]+s+back)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import numpy as np
H, W = map(int, input().split())

grid = [[] for h in range(H)]
for h in range(H):
    grid[h] = [-1 if _ == '#' else 0 for _ in input()]
    grid[h] = [-1] + grid[h] + [-1]
    #print(grid[h])
    count = 0
    for w in range(W + 1):
        if grid[h][w] == -1 and grid[h][w + 1] == 0:
            count = 1
            tmp = w + 1
        elif grid[h][w] == 0 and grid[h][w + 1] == 0:
            count += 1
        elif grid[h][w] == 0 and grid[h][w + 1] == -1:
            grid[h][tmp: w + 1] = [count] * (w + 1 - tmp)
            count = 0
    #print(grid)
#print(grid)
pad_grid = [[-1] * (W + 2)] + grid + [[-1] * (W + 2)]
#pad_grid
#print(pad_grid)
t_grid = np.transpose(pad_grid)

for h in range(1, W + 1):
    for w in range(H + 1):
        if t_grid[h][w] == -1 and t_grid[h][w + 1] != 0:
            count = 1
            tmp = w + 1
        elif t_grid[h][w] != -1 and t_grid[h][w + 1] != -1:
            count += 1
        elif t_grid[h][w] != -1 and t_grid[h][w + 1] == -1:
            t_grid[h][tmp: w + 1] += count - 1
            count = 0
    #print(t_grid)
print(max(t_grid.ravel()))

### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'

D = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
L = np.zeros((H, W), dtype=int)
R = np.zeros((H, W), dtype=int)

for h in range(H):
    U[h] = (U[h - 1] + 1) * S[h]
    D[-h - 1] = (D[-h] + 1) * S[-h - 1]
for w in range(W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w]
    R[:, -w - 1] = (R[:, -w] + 1) * S[:, -w - 1]
print(np.max(U + D + L + R) - 3)
### BUGGY CODE ###

n,s=open(0)
n=int(n)
a=s[0]<'W'>s[-2]
while n:a*=n;n-=1
l=1
r=f=0
for b,c in zip(s,s[1:-1]):f^=b==c;a=a*(l-r)**f%(10**9+7);r+=f;l+=f^1
print(a*(l==r))

### FIXED CODE ###

from math import*
M=10**9+7
n=int(input())
s=input()
if s[0]==s[-1]=='W':
  print(0)
  exit()
l=a=1
r=f=0
for b,c in zip(s,s[1:]):
  if b==c:
    f^=1
  if f:
    a*=l-r
    a%=M
    r+=1
  else:
    l+=1
print(a*factorial(n)%M*(l==r))
### BUGGY CODE ###

L,R = [int(x) for x in input().split()]
 
min_ans = 10**18
if R-L>=2019:
  min_ans=0

for i in range(L,R):
    for j in range(i+1,R+1):
        ans = (i*j)%2019
        
        if ans < min_ans:
            min_ans = ans
        if min_ans == 0:
            break
print(min_ans)


### FIXED CODE ###

L,R = [int(x) for x in input().split()]
 
min_ans = 10**18

if R-L>=2019:
  min_ans=0
else:
  for i in range(L,R):
      for j in range(i+1,R+1):
          ans = (i*j)%2019

          if ans < min_ans:
              min_ans = ans
          if min_ans == 0:
              break
print(min_ans)
### BUGGY CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
inf = float("inf")
dp = [inf] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = inf
for i in range(2,n):
    for j in range(i-k,i):
        a = dp[j] + abs(ls[j] - ls[i])
        if a < p:
            p = a
            a = 0
        else:
            a = 0
    dp[i] = p
    p = inf
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
dp = [10000000000] *n
dp[0] = 0
dp[1] = abs(ls[1]-ls[0])
p = 10000000000
for i in range(2,n):
    for j in range(i-k,i):
        if (dp[j] >= p) or (abs(ls[j] - ls[i]) >= p):
            pass
        else:
            a = dp[j] + abs(ls[j] - ls[i])
            if a < p:
                p = a
                a = 0
            else:
                a = 0
    dp[i] = p
    p = 10000000000
print(dp[n-1])