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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter
from bisect import bisect,bisect_left,insort

def solve(n, ppp):
    q = sorted(enumerate(ppp),key=itemgetter(1),reverse=True)
    le = [-1,-1,n,n]
    ans = 0
    for i, p in q:
        l_i = bisect(le,i)
        LL = le[l_i-2]
        LR = le[l_i-1]
        RL = le[l_i]
        RR = le[l_i+1]
        ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
        insort(le,i)
    return ans


n = int(readline())
ppp = list(map(int,readline().split()))
print(solve(n, ppp))

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter

n = int(readline())
ppp = list(map(int,readline().split()))

def BIT_add(i,x):
    while i <= n:
        tree[i] += x
        i += i&(-i)

def BIT_sum(i):
    s = 0
    while i:
        s += tree[i]
        i -= i&(-i)
    return s

def BIT_search(x):
    # 二分探索。和がx以上となる最小のインデックス(>= 1)を返す
      i = 0
      s = 0
      step = 1<<(n.bit_length()-1)
      while step:
          if i+step <= n and s + tree[i+step] < x:
              i += step
              s += tree[i]
          step >>= 1
      return i+1

q = sorted(enumerate(ppp,1),key=itemgetter(1),reverse=True)
tree = [0]*(n+1)

ans = 0
for i, p in q:
    L = BIT_sum(i) # 左にある既に書き込んだ数の個数
    BIT_add(i,1)
    R = n-p-L # 右にある既に書き込んだ数の個数
    LL = BIT_search(L-1) if L >= 2 else 0
    LR = BIT_search(L) if L >= 1 else 0
    RL = BIT_search(L+2) if R >= 1 else n+1
    RR = BIT_search(L+3) if R >= 2 else n+1
    ans += p*((LR-LL)*(RL-i)+(RR-RL)*(i-LR))
print(ans)
### BUGGY CODE ###

K,S=map(int,input().split())
ans=0
l=[i for i in range(K+1)]
for x in range(K+1):
  for y in range(K+1):
    if (S-x-y in l)==True:
      ans+=1
print(ans)

### FIXED CODE ###

K,S=map(int,input().split())
ans=0
for x in range(K+1):
  for y in range(K+1):
    if 0<=S-x-y<=K:
      ans+=1
print(ans)
### BUGGY CODE ###

N=int(input())
A=input().split()
A=[int(i) for i in A]
S=0
for i in range(N-1):
    for j in range(i+1,N):
        S+=A[i]*A[j]
print(S%(pow(10,9)+7))

### FIXED CODE ###

N=int(input())
A=input().split()
A=[int(i) for i in A]
S=0
A_sum=0
for i in range(N):
    A_sum+=A[i]
    

B=A_sum
for i in range(N):
    B-=A[i]
    S+=A[i]*B

print(S%(pow(10,9)+7))
### BUGGY CODE ###

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

total = 0
for i in range(n-1):
    for j in range(i+1, n):
        total = (((a[i] * a[j]) % 1000000007) + total) % 1000000007

print(total)


### FIXED CODE ###

mod = 1000000007

n = int(input())
a = list(map(int, input().split(' ')))
b = [0] * (n + 1)

for i, v in enumerate(a):
    b[i+1] = (b[i] + v) % mod

ans = 0
for i in range(n):
    ans = (((a[i] * (b[n] - b[i+1])) % mod) + ans) % mod

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

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

from itertools import accumulate
for i in range(k):
    imos = [0]*(n+1)
    for j in range(n):
        d = A[j]
        l = max(0, j-d)
        r = min(n-1, j+d)
        imos[l] += 1
        imos[r+1] -= 1
    imos = list(accumulate(imos))
    for j in range(n):
        A[j] = imos[j]
    if A == [n]*n:
        break

print(*A)


### FIXED CODE ###

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

from itertools import accumulate
for i in range(k):
    imos = [0]*(n+1)
    for j in range(n):
        d = A[j]
        l = max(0, j-d)
        r = min(n-1, j+d)
        imos[l] += 1
        imos[r+1] -= 1
    imos = list(accumulate(imos))
    for j in range(n):
        A[j] = imos[j]
    if A == [n]*n:
        break

print(*A)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

######################################################

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [-1] * (H * W)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B = sorted(B, key=lambda x: x[0])
C = [b[0] for b in B]

import bisect

for i in range(int(input())):
    l, r = [int(_) for _ in input().split()]
    pre = None
    ans = 0
    while l <= r:
        ni = bisect.bisect_left(C, l)
        # print(B[ni])
        if pre is not None:
            ans += abs(B[ni][1][0] - pre[0]) + abs(B[ni][1][1] - pre[1])
        l = l + D
        pre = (B[ni][1])
    print(ans)


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

######################################################

H, W, D = [int(_) for _ in input().split()]

A = [[int(_) for _ in input().split()]
     for _ in range(H)]

B = [None] * (H * W + 1)
for i in range(H):
    h = i * W
    for j in range(W):
        B[h + j] = (A[i][j], (i, j))
B[H * W] = (0, (-1, -1))
B = sorted(B, key=lambda x: x[0])
costs = [0] * (H * W + 1)
for i in range(H * W, 0, -1):
    if i + D <= H * W:
        costs[i] = costs[i + D] + abs(B[i][1][0] - B[i + D][1][0]) + abs(B[i][1][1] - B[i + D][1][1])

for i in range(int(input())):
    l,r = [int(_) for _ in input().split()]
    print(costs[l] - costs[r])
### BUGGY CODE ###

s = [i for i in input()]
n =len(s)
A=13

dp=[[0 for i in range(A+1)] for j in range(n+1)]
dp[0][0]=1

for i in range(n):
	for j in range(A+1):
		if s[i]!="?":
			if j-int(s[i])*10**(len(s)-(i+1))%13>=0:
				dp[i+1][j]=dp[i][j-int(s[i])*10**(len(s)-(i+1))%13]
			else:
				dp[i+1][j]=dp[i][j-int(s[i])*10**(len(s)-(i+1))%13+13]

		else:
			for c in range(10):
				if j-c*10**(len(s)-(i+1))%13>=0:
					dp[i+1][j]+=dp[i][j-c*10**(len(s)-(i+1))%13]
				else:
					# print(j-c%13+13)
					dp[i+1][j]+=dp[i][j-c*10**(len(s)-(i+1))%13+13]

			
			

print(dp[n][5]%(10**9+7))
				


### FIXED CODE ###

S = input()
dp = [[0]*13 for i in range(len(S))]
MOD = 10**9+7
 
if S[0]=='?':
    for i in range(10):
        dp[0][i] = 1
else:
    dp[0][int(S[0])] = 1
 
for i,c in enumerate(S[1:]):
    for j in range(13):
        if c=='?':
            for k in range(10):
                nj = (j*10 + k) % 13
                dp[i+1][nj] += dp[i][j]
                dp[i+1][nj] %= MOD
        else:
            nj = (j*10 + int(c)) % 13
            dp[i+1][nj] += dp[i][j]
            dp[i+1][nj] %= MOD
 
print(dp[-1][5])
### BUGGY CODE ###

n = input()
a = [int(i) for i in input().split()]
q = int(input())
bb = []
cc = []
for i in range(q):
    btmp, ctmp = [int(j) for j in input().split()]
    bb.append(btmp)
    cc.append(ctmp)

def temp(b,c,i):
    if i==b:
        return c
    else:
        return i

atol = sum(a)
for b,c in zip(bb,cc):
    
    count = len([ i for i in a  if i == b])
    a = [ temp(b,c,i) for i in a ]
    atol +=  (c - b) * count
    print(atol)


### FIXED CODE ###

n = input()
a = [int(i) for i in input().split()]
q = int(input())
bb = []
cc = []
for i in range(q):
    btmp, ctmp = [int(j) for j in input().split()]
    bb.append(btmp)
    cc.append(ctmp)


amap = {}
for i in a :
    if i not in amap :
        amap[i] = 1
    else:
        amap[i] += 1

atol = sum(a)

for b,c in zip(bb,cc):
    
    if b in amap:
        atol +=  (c - b) * amap[b]
    
        if c in amap :
            amap[c] += amap[b]
        else:
            amap[c] = amap[b]
        
        amap.pop(b)
        
    print(atol)
### BUGGY CODE ###

def power(x, y, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    二分累乗法でx ** yを求める
    
    2 ** n = 4 ** (n//2) = 16 ** (n//4)
    みたいなことをする
    """

    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2, mod)**2 % mod
    else            : return power(x, y//2, mod)**2 * x % mod


def mul(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味したかけ算を行う
    """
    return ((a % mod) * (b % mod)) % mod

def div(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味した割り算を行う    
    """
    if a == b:
        return 1
    return mul(a, power(b, mod-2, mod), mod)


def factorial_part(start, last, mod):
    """
    startからlastまでのかけ算を行う
    
    factorial_part(2, 4, mod) = 2 * 3 * 4 = 24    
    """
    assert(start <= last)
    x = 1
    for k in range(start, last+1):
        x *= k
        x %= mod
    return x

def combination(n, a, mod):
    if a == 0:
        return 1
    nCa = div(factorial_part(n - a + 1, n, mod), factorial_part(1, a, mod), mod)
    return nCa

n, m, k = list(map(int, input().split()))
mod =  998244353

powers = [0] * n
a = m
for kk in range(n):
    powers[kk] = a
    a = (a * (m - 1)) % mod

c =0
p = 1
comb = 1
kk = 0
a = n - kk
c += powers[a - 1] * comb

for kk in range(1, k + 1):
    a = n - kk
    comb = (div(comb,  kk, mod) * (a))%mod
    c = c + powers[a - 1] * comb
    c = c%mod
print(c)

### FIXED CODE ###

def power(x, y, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    二分累乗法でx ** yを求める
    
    2 ** n = 4 ** (n//2) = 16 ** (n//4)
    みたいなことをする
    """

    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2, mod)**2 % mod
    else            : return power(x, y//2, mod)**2 * x % mod


def mul(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味したかけ算を行う
    """
    return ((a % mod) * (b % mod)) % mod

def div(a, b, mod):
    """
    https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
    modを加味した割り算を行う    
    """
    if a == b:
        return 1
    return mul(a, inv_t[b], mod)


def factorial_part(start, last, mod):
    """
    startからlastまでのかけ算を行う
    
    factorial_part(2, 4, mod) = 2 * 3 * 4 = 24    
    """
    assert(start <= last)
    x = 1
    for k in range(start, last+1):
        x *= k
        x %= mod
    return x

def combination(n, a, mod):
    if a == 0:
        return 1
    nCa = div(factorial_part(n - a + 1, n, mod), factorial_part(1, a, mod), mod)
    return nCa

n, m, k = list(map(int, input().split()))
mod =  998244353

P = mod
N = max([max([n, m]), k]) + 5
inv_t = [0]+[1]
for i in range(2,N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

powers = [0] * n
a = m
for kk in range(n):
    powers[kk] = a
    a = (a * (m - 1)) % mod

c =0
p = 1
comb = 1
kk = 0
a = n - kk
c += powers[a - 1] * comb

for kk in range(1, k + 1):
    a = n - kk
    comb = (div(comb,  kk, mod) * (a))%mod
    c = c + powers[a - 1] * comb
    c = c%mod
print(c)
### BUGGY CODE ###

#%%
inf = 10**9 + 7

n = int(input())
a = list(map(int, input().split()))
count = [0] * 70
for i in range(n):
    tmp = list(str(bin(a[i])[2:]))[::-1]
    #print(tmp)
    for j in range(len(tmp)):
        if tmp[j] == '1':
            k = 69 - j
            count[k] += 1

#print(count)

ans = 0
for i in range(70):
    k = 2 ** (69 - i)
    k %= inf
    x = count[i] % inf
    y = (n - x) % inf
    ans += (x * y * k) % inf
    ans %= inf

ans %= inf
print(ans)



# %%


### FIXED CODE ###

#%%
inf = 10**9 + 7

n = int(input())
a = list(map(int, input().split()))
count = [0] * 70
for i in range(n):
    tmp = list(str(bin(a[i])[2:]))[::-1]
    #print(tmp)
    for j in range(len(tmp)):
        if tmp[j] == '1':
            k = 69 - j
            count[k] += 1

#print(count)

ans = 0
for i in range(70):
    k = 2 ** (69 - i)
    k %= inf
    x = count[i] % inf
    y = (n - x) % inf
    ans += (x * y * k) % inf
    ans %= inf

ans %= inf
print(ans)



# %%
### BUGGY CODE ###

n,x,y = map(int,input().split())
ans = [0]*(n-1)
for i in range(n):
    tbl = [0]*n
    for j in range(i,n):
        tbl[j] = min(abs(j+1-i-1),abs(i+1-x)+1+abs(j+1-y))
    for i in range(1,n):
        ans[i-1] += tbl.count(i)
[print(i) for i in ans]

### FIXED CODE ###

n,x,y = map(int,input().split())
ans = [0]*(n)
for i in range(n):
    tbl = [0]*n
    for j in range(i,n):
        tbl[j] = min(abs(j+1-i-1),abs(i+1-x)+1+abs(j+1-y))
        ans[tbl[j]] += 1
[print(i) for i in ans[1:]]
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

from collections import deque

N = int(input())
S = [input() for _ in range(N)]

def bfs(start):
    res = 0
    dist = [-1] * N
    dist[start] = 1
    q = deque()
    q.append([start, 1])

    while q:
        i, d = q.popleft()
        if dist[i] == -1:
            dist[i] = d
            res = max(res, d)
        elif dist[i] != d:
            res = -1
            break
        for j in range(N):
            if S[i][j] == '1' and dist[j] != d-1:
                q.append([j, d+1])
    return res

ans = -1
for i in range(N):
    k = bfs(i)
    if k == -1:
        break
    else:
        ans = max(ans, k)

print(ans)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

from collections import deque

N = int(input())
S = [input() for _ in range(N)]

def bfs(start):
    res = 0
    dist = [-1] * N
    dist[start] = 1
    q = deque()
    q.append([start, 1])
    st = set()
    st.add((start, 1))

    while q:
        i, d = q.popleft()
        if dist[i] == -1:
            dist[i] = d
            res = max(res, d)
        elif dist[i] != d:
            res = -1
            break
        for j in range(N):
            if S[i][j] == '1' and dist[j] != d-1:
                if (j, d+1) not in st:
                    q.append([j, d+1])
                    st.add((j, d+1))
    return res

ans = -1
for i in range(N):
    k = bfs(i)
    if k == -1:
        break
    else:
        ans = max(ans, k)

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

n=int(input())
a=list(map(int,input().split()))
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  a=[c if b==j else j for j in a]
  print(sum(a))

### FIXED CODE ###

import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))
a0,a1= np.unique(a,return_counts=True)
suma=np.sum(a)
a2=np.array([0]*100001)
for j in range(a0.size):
  a2[a0[j]]=a1[j]
#print(suma)
#print(a0)
#print(a1)
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  sumb=a2[b]
  a2[b]=0
  a2[c]+=sumb
  sumc=sumb*(c-b)
  suma+=sumc
  print(suma)
### BUGGY CODE ###

from collections import Counter


def make_divisors(n):

    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if i != n and i in c:
                return False

            tmp = n // i
            if i != tmp:
                if tmp != n and tmp in c:
                    return False
    return True


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

c = Counter(A)
ans = 0
for a in A:
    # 同じ数が複数ある
    if c[a] >= 2:
        continue

    # 約数を取得
    if make_divisors(a):
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

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

c = Counter(A)
p = [True]*(10**6+1)

for k, v in c.items():
    t = k*2
    while t <= 10**6:
        p[t] = False
        t += k

ans = 0
for a in A:
    if c[a] == 1 and p[a]:
        ans += 1
print(ans)
### BUGGY CODE ###

def permutations(S):
    if len(S) == 1:
        return S
    res = []
    for i, s in enumerate(S):
        P = permutations(S[:i] + S[i+1:])
        for p in P:
            res.append(f'{s}{p}')
    return res

if __name__ == '__main__':
    n, l = [int(x) for x in input().split(' ')]
    S = [input() for i in range(0, n)]
    print(min(permutations(S)))
    

### FIXED CODE ###

if __name__ == '__main__':
    n, l = [int(x) for x in input().split(' ')]
    S = [input() for i in range(0, n)]
    print(''.join(sorted(S)))
### BUGGY CODE ###

x = int(input())

a = -1
b = 0

while True:
    a5 = pow(a, 5)
    b5 = pow(b, 5)
    if(a5-b5 == x):
        print("{} {}".format(a, b))
        break
    if(a5+b5 == x):
        print("{} {}".format(a, -b))
        break
    if(-a5-b5 == x):
        print("{} {}".format(-a, b))
        break
    if(-a5+b5 == x):
        print("{} {}".format(-a, -b))
        break

    b += 1
    if(a==b):
        a +=1
        b =0


### FIXED CODE ###

x = int(input())

a = 0
b = -1

while True:
    a5 = pow(a, 5)
    b5 = pow(b, 5)
    if(a5-b5 == x):
        print("{} {}".format(a, b))
        break
    if(a5+b5 == x):
        print("{} {}".format(a, -b))
        break
    if(-a5-b5 == x):
        print("{} {}".format(-a, b))
        break
    if(-a5+b5 == x):
        print("{} {}".format(-a, -b))
        break

    b += 1
    if(a==b-1):
        a +=1
        b =0
### BUGGY CODE ###

#<C>
from collections import Counter
import itertools
N = int(input())
lan = [Counter(list(input())) for n in range(N)]
#print(lan)
ans = 0
for l in itertools.combinations(lan, 2):
    if l[0] == l[1]:
        ans += 1

print(ans)



### FIXED CODE ###

import collections

N = int(input())
lan = ["".join(sorted(input())) for n in range(N)]
#print(lan)
lans = collections.Counter(lan)
#print(lans)
ans = 0
for si in set(lan):
    n = lans[si]
    ans += n * (n - 1) // 2
print(ans)
### BUGGY CODE ###

import sys

def cost(N, A, b):
	return sum([abs(A[i] - b - i - 1) for i in range(N)])

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

res = float("inf")
b = 0
if cost(N, A, b) <= cost(N, A, b - 1) and  cost(N, A, b) <= cost(N, A, b + 1):
	print cost(N, A, b)
	sys.exit()
elif cost(N, A, b) < cost(N, A, b + 1):
	delta = -1
else:
	delta = 1
b += delta
pre_delta = delta
while pre_delta == delta:
	if cost(N, A, b) < cost(N, A, b + delta):
		break
	b += delta
print cost(N, A, b)


### FIXED CODE ###

import sys

N = input()
A = map(int, raw_input().split())
A = [A[i] - i - 1 for i in range(N)]
A.sort()
b = A[N / 2]
print sum([abs(a - b) for a in A])
### BUGGY CODE ###

H,W=map(int, input().split())
L=[]
for h in range(H):
    l=list(input())
    L.append(l)
D=[(1,0),(0,1),(-1,0),(0,-1)]
ans=[[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if L[h][w]==".":
            que=[(h,w)]
            done=[]
            flag=False
            while len(que)>0:
                nowh,noww=que.pop(0)
                for d in D:
                    dh,dw=d
                    newh=nowh+dh
                    neww=noww+dw
                    if 0<=newh<H and 0<=neww<W:
                        if L[newh][neww]=="#":
                            ans[h][w]=abs(newh-h)+abs(neww-w)
                            flag=True
                            break
                        elif ((newh,neww) not in done):
                            que.append((newh,neww))
                            done.append((newh,neww))
                if flag:
                    break
import numpy as np
ans=np.array(ans)
print(ans.max())



### FIXED CODE ###

from collections import deque
H,W=map(int, input().split())

A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0

d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)



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

N = int(input())
list = []
for i in range(N//2):
    if(N%(i+1) == 0):
        list.append([i+1, N//(i+1)])
min = 1000000000000
for i in list:
    if(min > i[0]+i[1]):
        min = i[0]+i[1]
print(min-2)

### FIXED CODE ###

import math
N = int(input())
list = []
for i in range(int(math.sqrt(N))):
    if(N%(i+1) == 0):
        list.append([i+1, N//(i+1)])
min = 1000000000000
for i in list:
    if(min > i[0]+i[1]):
        min = i[0]+i[1]
print(min-2)
### BUGGY CODE ###

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

ans = 10000000000
X = sum(a)

for i in range(N-1):
    sa = abs(X - 2*sum(a[:i+1]))
    ans = min(ans,sa)

print(ans)


### FIXED CODE ###

input()
cards = tuple(map(int, input().split(' ')))

a = sum(cards[1:])
s = cards[0]
diff_min = abs(a - s)

for card in cards[1:-1]:
    a -= card
    s += card
    diff_min = min(diff_min, abs(a - s))

print(diff_min)
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[float('inf')]*w for i in range(h)]

d=deque()
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            d.append([i,j])
            itta[i][j]=0

# print(d)
# print(itta)
while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==float('inf'):
                    itta[nh+d1][nw+d2]=cnt
                    d.append([nh+d1,nw+d2])
    # print(d)

# print(itta)
print(cnt-1)

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

cnt=0

itta=[[10**9]*w for i in range(h)]

d=deque()
aaa=d.append
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            aaa([i,j])
            itta[i][j]=0

# print(d)
# print(itta)

while d:
    cnt+=1
    for l in range(len(d)):
        nh,nw=d.popleft()
        for i in range(4):
            d1,d2=direction[i]
            if 0<=nh+d1<h and 0<=nw+d2<w:
                if itta[nh+d1][nw+d2]==10**9:
                    itta[nh+d1][nw+d2]=cnt
                    aaa([nh+d1,nw+d2])
    # print(d)

# print(itta)
print(cnt-1)
### BUGGY CODE ###

n=int(input())
s=input()
ans=float("inf")
for i in range(n+1):
  a=s[:i].count("#")+s[i:].count(".")
  ans=min(ans,a)
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
a=s.count(".")
ans=a
for i in range(n):
  if s[i]==".":
    a-=1
  else:
    a+=1
  ans=min(ans,a)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    nums = [0] * N
    for i in A:
        nums[int(i) - 1] += 1
    
    #print(nums)
    for k in range(0, N):
        nums[int(A[k]) - 1] -= 1
        #print("aaa" + str(k))
        #print(nums)
        sum = 0
        for num in nums:
            sum += num * ( num - 1 ) // 2
        print(sum)
        nums[int(A[k]) - 1] += 1
    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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]"):
    nums = [0] * N
    for i in A:
        nums[int(i) - 1] += 1
    
    sum = 0
    for num in nums:
        sum += num * ( num - 1 ) // 2

    for k in range(0, N):
        old = nums[int(A[k]) - 1]
        new = old - 1
        ans = sum - (old * (old - 1) // 2 - new * (new - 1) // 2)
        print(ans)
    

    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
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()