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

import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i-1, 0, -1):
        plus = l[i]+l[j]
        minus = l[i]-l[j]
        lj = l[:j]
        bir = bisect.bisect(lj, plus)
        bil = bisect.bisect(lj, minus)
        cnt += bir-bil
print(cnt)

### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i-1, 0, -1):
        plus = l[i]+l[j]
        minus = l[i]-l[j]
        bir = min(j, bisect.bisect(l, plus))
        bil = bisect.bisect(l, minus)
        if bir > bil:
            cnt += bir-bil
print(cnt)
### BUGGY CODE ###

MOD = 10**9+7
k = int(input())
s = input()
n = len(s)


def com(n, r):
    X = Y = 1
    if r < 0 or n < r:
        return 0
    if n-r < r:
        r = n-r
    for i in range(1, r+1):
        Y = Y*i % MOD
        X = X*(n-i+1) % MOD
    Y = pow(Y, MOD-2, MOD)
    return X*Y % MOD


ans = 0
for x in range(k+1):
    ans += pow(26, x, MOD)*com(n+k-x-1, n-1)*pow(25, k-x, MOD)
print(ans % MOD)

### FIXED CODE ###

MOD = 10**9+7
k = int(input())
s = input()
n = len(s)


U = n+k
fact = [0]*(U+1)
fact[0] = 1
for i in range(1, U+1):
    fact[i] = fact[i-1]*i % MOD


invfact = [0]*(U+1)
invfact[U] = pow(fact[U], MOD-2, MOD)
for i in reversed(range(U)):
    invfact[i] = invfact[i+1]*(i+1) % MOD


def nCr(n, r):
    if r < 0 or n < r:
        return 0
    return fact[n]*invfact[r]*invfact[n-r]


ans = 0
for x in range(k+1):
    ans += pow(26, x, MOD)*nCr(n+k-x-1, n-1)*pow(25, k-x, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from bisect import bisect

def main():
    q = II()
    Q = []
    for _ in range(q):
        Q.append(LI())
    A = []
    bias = 0
    for q in Q:
        if q == [2]:
            idx = (len(A) - 1) // 2
            ans = A[idx], (sum(A[len(A) - idx - 1:]) - sum(A[:idx + 1]) + bias)
            print(*ans)
        else:
            _, a, b = q
            bias += b
            index = bisect(A, a)
            A.insert(index, a)
    return

main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from heapq import heappush, heappop

def main():
    q = II()
    Q = []
    for _ in range(q):
        Q.append(LI())
    lows, highs = [], []
    slow, shigh = 0, 0
    bias = 0
    for q in Q:
        if q[0] == 2:
            odd = -lows[0] if len(highs) != len(lows) else 0
            ans = -lows[0], bias + shigh - slow + odd
            print(*ans)
        else:
            _, a, b = q
            bias += b
            if not lows:
                lows = [-a]
                slow = a
            else:
                if a <= -lows[0]:
                    heappush(lows, -a)
                    slow += a
                    if len(lows) > len(highs) + 1:
                        x = -heappop(lows)
                        heappush(highs, x)
                        slow -= x
                        shigh += x
                else:
                    heappush(highs, a)
                    shigh += a
                    if len(highs) > len(lows):
                        x = heappop(highs)
                        heappush(lows, -x)
                        shigh -= x
                        slow += x
    return

main()
### BUGGY CODE ###

from collections import defaultdict

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

B = sorted([(A[i], i + 1) for i in range(N)], reverse=True)
dp = defaultdict(int)

for S in range(1, N + 1):
    for x in range(S + 1):
        y = S - x
        candid = []
        if x >= 1:
            candid.append(dp[(x - 1, y)] + B[S - 1][0]
                          * (B[S - 1][1] - x))
        if y >= 1:
            candid.append(dp[(x, y - 1)] + B[S - 1][0]
                          * ((N - y + 1) - B[S - 1][1]))
        dp[(x, y)] = max(candid)

print(max([dp[(i, N - i)] for i in range(N + 1)]))


### FIXED CODE ###

from collections import defaultdict

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

B = sorted([(A[i], i + 1) for i in range(N)], reverse=True)
dp = defaultdict(int)

for S in range(1, N + 1):
    for x in range(S + 1):
        y = S - x
        candid = []
        if x >= 1:
            candid.append(dp[(x - 1, y)] + B[S - 1][0]
                          * (B[S - 1][1] - x))
        if y >= 1:
            candid.append(dp[(x, y - 1)] + B[S - 1][0]
                          * ((N - y + 1) - B[S - 1][1]))
        dp[(x, y)] = max(candid)

print(max([dp[(i, N - i)] for i in range(N + 1)]))
### BUGGY CODE ###

import itertools

n, k = map(int,input().split())
ans = 0
li = list(range(n+1))

for i in range(k,n+2):
    x = list(itertools.combinations(li, i))
    y = []
    for c in x:
        y.append(sum(c))
    ans += len(set(y))

print(ans%(10**9+7))

### FIXED CODE ###

import itertools

n, k = map(int,input().split())
ans = 0
li = list(range(n+1))

for i in range(k,n+2):
    a = int(1/2*i*(i-1))
    b = n*i-(int(1/2*i*(i-1)))
    ans += b - a + 1

print(ans%(10**9+7))
### BUGGY CODE ###

import sys
from collections import defaultdict
def main():
    input = sys.stdin.readline
    n = int(input())
    nums_table = defaultdict(int)
    ans = 0
    for i in range(1, n+1):
        nums_table[i] = 2
    nums_table[1] = 1
    for i in range(2, n//2+1):
        for j in range(2*i,n+1,i):
            nums_table[j] += 1
    for i in range(1, n+1):
        ans += i * nums_table[i]
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    nums_table = [2] * (n+1)
    ans = 0
    for i in range(1, n+1):
        nums_table[i] = 2
    nums_table[1] = 1
    for i in range(2, n//2+1):
        for j in range(2*i,n+1,i):
            nums_table[j] += 1
    for i in range(1, n+1):
        ans += i * nums_table[i]
    print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N,W = map(int,input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  _w,_v = map(int,input().split())
  for w in range(W+1):
    if w-_w >= 0:
      dp[i+1][w] = max(dp[i][w],dp[i][w-_w]+_v)
    else:
      dp[i+1][w] = dp[i][w]

print(dp[N][W])

### FIXED CODE ###

import numpy as np

N,W = map(int,input().split())
w,v = [0]*N ,[0]*N
arr = [map(int,input().split()) for _ in range(N)]
dp = np.zeros(W+1,dtype= np.int64)

for w,v in arr:
    np.maximum(dp[:-w] + v, dp[w:], out = dp[w:])
print(dp[-1])
### BUGGY CODE ###

from collections import Counter

def main():
  s = input().strip()
  remains = Counter([int(s[-i:]) % 2019 for i in range(1, len(s)+1)]).items()

  cnt = 0
  for k, v in remains:
    cnt += (v * (v - 1)) // 2
    if k == 0:
      cnt += v
  print(cnt)
  
if __name__=='__main__':
  main()


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding:utf-8 -*-

def main():
  s = input().strip()
  x = remain = 0
  remains = [0] * 2019
  k = 1
  for d in map(int, list(s[::-1])):
    x = d * k + remain
    remain = x % 2019
    k = (10 * k) % 2019
    remains[remain] += 1

  print(sum([(remain * (remain - 1)) // 2 for remain in remains]) + remains[0])
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while ng - ok > 1 and c < 100000:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))


### FIXED CODE ###

# サンプル3
# 6
# 6 5 4 3 2 1
# b=3で2+0+2+4+6+8 = 22 b=4で1+1+3+5+7+9=26
# わからんからコード書いて試す
n = int(input())
a = list(map(int, input().split()))
# for b in range(-10, 10):
#     tmp = 0
#     for i, v in enumerate(a):
#         tmp += abs(v - (b + i + 1))
#     print(f"b={b}, tmp={tmp}")
# でかくても小さくてもダメっぽい
# 三分探索？やったことないしやり方わからんからググる
# めぐる式にこれhttps://qiita.com/ganariya/items/1553ff2bf8d6d7789127をしただけ

ok, ng = -10**9, 10**9 + 1


def calc(b):
    ret = 0
    for i, v in enumerate(a):
        ret += abs(v - (b + i + 1))
    return ret


# なぜかTLEなるのでカウンタを設置してみた
c = 0
while c < 100:
    c += 1
    c1 = (2 * ok + ng) // 3
    c2 = (ok + 2 * ng) // 3
    b1, b2 = calc(c1), calc(c2)
    if b1 > b2:
        ok = c1 + 1  # +1のきもちは不明
    else:
        ng = c2

print(calc(ok))
### BUGGY CODE ###

N, K = list(map(int, input().split()))
A = list(map(lambda x: int(x) - 1, input().split()))

v = [A[:]]
now = 0
for i in range(60):
    v.append([v[i][v[i][j]] for j in range(N)])
    if K>>i & 1:
        now = v[i][now]
print(now + 1)

### FIXED CODE ###

N, K = list(map(int, input().split()))
K -= 1
A = list(map(lambda x: int(x) - 1, input().split()))
seen = [None]*N
seen_set = set()
now = 0
for i in range(N):
    seen[i] = now
    seen_set.add(now)
    to = A[now]
    now = to
    if now in seen_set:
        seen[i+1] = now
        loop_s = seen.index(now)
        loop_end = i + 1
        size = loop_end - loop_s
        break
if K <= loop_s:
    print(seen[K+1] + 1)
else:
    K -= loop_s
    print(seen[loop_s + 1 + K % size] + 1)
### BUGGY CODE ###

#https://atcoder.jp/contests/abc134/tasks/abc134_d
n = int(int(input()))
a = [int(i) for i in input().split()]

b = [0] * n
for i in reversed(range(1, n + 1)):
    cnt = 0
    c = []
    for j in range(1, n + 1):
        if j % i == 0 and j != i:
            cnt += 1
            c.append(j)
    s = 0
    for j in c:
        s += a[j - 1]
    #print(i, cnt, c, s)
    if s % 2 == a[i - 1]:
        b[i - 1] = 0
    else:
        b[i - 1] = 1
#print(b)
e = sum(b)
print(e)

if e != 0:
    d = []
    for i in range(n):
        if b[i] == 1:
            d.append(i + 1)
    print(' '.join(map(str, d)))

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
arr = [0 for _ in range(n)]
for i in reversed(range(n)):
    s = 0
    for j in range(i, n, i+1):
        s += arr[j]
    s %= 2
    if a[i] != s:
        arr[i] = 1
print(sum(arr))
for i in range(n):
    if arr[i] == 1:
        print(i+1, end=' ')
print('')
### BUGGY CODE ###

m=input();n=int(m);a=[];i=6
while n%2==0:a+=[2];n//=2
while n%3==0:a+=[3];n//=3
while i<n+2:
 if n%(i-1)==0:a+=[i-1];n//=i-1
 elif n%(i+1)==0:a+=[i+1];n//=i+1
 else:i+=6
print(m+':',*a)


### FIXED CODE ###

p=lambda x:print(x,end=' ')
n=input();p(n+':')
m=n=int(n)
while n%2==0 and n>3:p(2);n//=2
d=3
while d*d<m and n>d:
 if n%d>0:d+=2
 else:p(d);n//=d
print(n)
### BUGGY CODE ###

import sys
mod=1000000007
n=int(input())
s=str(input())
ans=1
for i in range(1,n+1):
  i=i%mod
  ans=ans*i
  ans=ans%mod
d={"B":1,"W":0}
sg=[]
now=1
ss=0
gg=0
for i in range(n):
  if d[s[i]]==now%2:
    sg.append("S")
    now+=1
    ss+=1
  else:
    sg.append("G")
    now-=1
    gg+=1
now=1
sg1=[]
for i in range(1,n+1):
  #print("now",now,s[-1*i])
  if d[s[-1*i]]==now%2:
    sg1.insert(0,"G")
    now+=1
    gg+=1
  else:
    sg1.insert(0,"S")
    now-=1
    ss+=1
sg2=sg+sg1
#print(sg2)
sss=0
for i in sg2:
  if i=="S":
    sss+=1
  else:
    if sss>=0:
      ans*=sss
      ans=ans%mod
      sss-=1
    else:
      print(0)
      sys.exit()
  #print(i,ans,sss)      
if sss==0:
  print(ans)
else:
  print(0)
    

### FIXED CODE ###

import sys
mod=1000000007
n=int(input())
s=str(input())
ans=1
for i in range(1,n+1):
  i=i%mod
  ans=ans*i
  ans=ans%mod
d={"B":1,"W":0}
sg=[]
now=1
sss=0
for i in range(2*n):
  if d[s[i]]==now%2:
    sss+=1
    now+=1
    a="S"
  else:
    a="G"
    now-=1
    if sss>=0:
      ans*=sss
      ans=ans%mod
      sss-=1
    else:
      ans=0
  #print("i",i,a,sss,ans)
if sss==0:
  print(ans)
else:
  print(0)
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

A = list(map(int, input()))
N = len(A)
mod = 2019

dp0 = list2d(2, mod, 0)
dp1 = list2d(2, mod, 0)
dp2 = list2d(2, mod, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    dp0[(i+1)&1][0] = dp0[i&1][0]
    dp1[(i+1)&1][a] = dp0[i&1][0]
    for j in range(mod):
        nxt = (j*10+a) % mod
        dp1[(i+1)&1][nxt] += dp1[i&1][j]
        dp2[(i+1)&1][nxt] += dp1[i&1][j]
        dp2[(i+1)&1][j] += dp2[i&1][j]
    dp0[i&1] = [0] * mod
    dp1[i&1] = [0] * mod
    dp2[i&1] = [0] * mod
ans = dp2[N&1][0]
print(ans)


### FIXED CODE ###

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = input()
N = len(S)
mod = 2019

acc = [0] * (N+1)
mul = 1
for i in range(N-1, -1, -1):
    x = int(S[i]) * mul
    acc[i] = (acc[i+1] + x) % mod
    mul *= 10
    mul %= mod

C = Counter(acc)
ans = 0
for v in C.values():
    ans += v*(v-1) // 2
print(ans)
### BUGGY CODE ###

import bisect

n = int(input())
li = list(map(int, input().split()))
ans = 0

li.sort()

for a, aa in enumerate(li):
  if a < n - 2:
    for b, bb in enumerate(li[a+1:]):
      cnt = bisect.bisect_left(li[a+1+b+1:], aa + bb)
      ans += cnt
            
print(ans)

### FIXED CODE ###

import bisect

n = int(input())
li = list(map(int, input().split()))
ans = 0

li.sort()

for i in range(n):
  for j in range(i+1, n):
    cnt = bisect.bisect_left(li, li[i]+li[j])
    ans += cnt - j - 1
            
print(ans)
### BUGGY CODE ###

import numpy as np
def inpl(): return list(map(int,input().split()))

N, M , Q = inpl()
#trains = np.zeros((N+1,N+1),dtype=np.int)
cumsum = np.zeros((N+1,N+1),dtype=np.int)
ans = np.zeros((N+1,N+1),dtype=np.int)

for i in range(M):
    L, R = inpl()
    cumsum[L,R] += 1

for l in range(1,N+1):
    for r in range(1,N+1):
        cumsum[l,r] += cumsum[l-1,r] + cumsum[l,r-1] - cumsum[l-1,r-1]

for l in range(1,N+1):
    for r in range(l,N+1):
        ans[l,r] = cumsum[r,r] - cumsum[l-1,r] - cumsum[r,l-1] + cumsum[l-1,l-1]

for i in range(Q):
    p, q = inpl()
    print(ans[p,q])

### FIXED CODE ###

def inpl(): return list(map(int,input().split()))

N, M, Q = inpl()
cumsum = [0]*((N+1)**2)
ans = [0]*((N+1)**2)

for i in range(M):
    L, R = inpl()
    cumsum[L*(N+1)+R] += 1

for l in range(1,N+1):
    for r in range(1,N+1):
        cumsum[l*(N+1)+r] += cumsum[(l-1)*(N+1)+r] + cumsum[l*(N+1)+r-1] - cumsum[(l-1)*(N+1)+r-1]

for l in range(1,N+1):
    for r in range(l,N+1):
        ans[l*(N+1)+r] = cumsum[r*(N+1)+r] - cumsum[(l-1)*(N+1)+r] - cumsum[r*(N+1)+l-1] + cumsum[(l-1)*(N+1)+l-1]

for i in range(Q):
    p, q = inpl()
    print(ans[p*(N+1)+q])
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) - 1 for i in range(Q)]
print(*["Yes" if Q < K + A.count(a) else "No" for a in range(N)], sep='\n')


### FIXED CODE ###

from sys import stdin
from collections import Counter

lines = stdin.readlines()

N, K, Q = map(int, lines[0].split())
ans = [0] * N
A = Counter((int(i) - 1 for i in lines[1:]))
for k in A.keys():
    ans[k] += A[k]
print("\n".join(("Yes" if Q < K + a
                 else "No" for a in ans)))
### BUGGY CODE ###

# LCS(Longest common subsequence)
s = input()
t = input()

def lcs(str1, str2):
    len1, len2 = len(str1), len(str2)
    lcs_dp = [[0]*(len2+1) for i in range(len1+1)]
    for i in range(len1-1, -1, -1):
        for j in range(len2-1, -1, -1):
            r = max(lcs_dp[i+1][j], lcs_dp[i][j+1])
            if str1[i] == str2[j]:
                r = max(r, lcs_dp[i+1][j+1]+1)
            lcs_dp[i][j] = r
    res = []
    i, j = 0, 0
    while i < len1 and j < len2:
        if str1[i] == str2[j]:
            res.append(str1[i])
            i += 1; j += 1
        elif lcs_dp[i][j] == lcs_dp[i+1][j]:
            i += 1
        elif lcs_dp[i][j] == lcs_dp[i][j+1]:
            j += 1
    return ''.join(res)

print(lcs(s, t))

### FIXED CODE ###

# LCS(Longest common subsequence)
s = input()
t = input()

def lcs(str1, str2):
    len1, len2 = len(str1), len(str2)
    lcs_dp = [[0]*(len2+1) for i in range(len1+1)]
    for i in range(len1-1, -1, -1):
        for j in range(len2-1, -1, -1):
            r = max(lcs_dp[i+1][j], lcs_dp[i][j+1])
            if str1[i] == str2[j]:
                r = max(r, lcs_dp[i+1][j+1]+1)
            lcs_dp[i][j] = r
    res = []
    i, j = 0, 0
    while i < len1 and j < len2:
        if str1[i] == str2[j]:
            res.append(str1[i])
            i += 1; j += 1
        elif lcs_dp[i][j] == lcs_dp[i+1][j]:
            i += 1
        elif lcs_dp[i][j] == lcs_dp[i][j+1]:
            j += 1
    return ''.join(res)

print(lcs(s, t))
### BUGGY CODE ###

H,W = map(int,input().split())
maze = []
from collections import deque
for _ in range(H):
    s = list(input())
    maze.append(s)
direction = [[1,0],[0,1],[-1,0],[0,-1]]
ans = -1
for row in range(H):
    for col in range(W):
        if maze[row][col] == "#":
            continue
        distance = [[-1 for _ in range(W)] for _ in range(H)]
        d = deque([[row,col]])
        distance[row][col] = 0
        while(len(d)>0):
            nowrow, nowcol = d.popleft()
            for subrow, subcol in direction:
                subrow += nowrow
                subcol += nowcol
                if subrow < 0 or subrow >= H or subcol < 0 or subcol >= W:
                    continue
                if maze[subrow][subcol] == "#":
                    continue
                if distance[subrow][subcol] != -1:
                    continue
                d.append([subrow, subcol])
                distance[subrow][subcol] = distance[nowrow][nowcol] + 1
            ans = max(ans,max([max(maxrow) for maxrow in distance]))
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
maze = []
from collections import deque
for _ in range(H):
    s = list(input())
    maze.append(s)
direction = [[1,0],[0,1],[-1,0],[0,-1]]
ans = -1
for row in range(H):
    for col in range(W):
        if maze[row][col] == "#":
            continue
        distance = [[-1 for _ in range(W)] for _ in range(H)]
        d = deque([[row,col]])
        distance[row][col] = 0
        while(len(d)>0):
            nowrow, nowcol = d.popleft()
            for subrow, subcol in direction:
                subrow += nowrow
                subcol += nowcol
                if subrow < 0 or subrow >= H or subcol < 0 or subcol >= W:
                    continue
                if maze[subrow][subcol] == "#":
                    continue
                if distance[subrow][subcol] != -1:
                    continue
                d.append([subrow, subcol])
                distance[subrow][subcol] = distance[nowrow][nowcol] + 1
            ans = max(ans,max([max(maxrow) for maxrow in distance]))
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
 
ans = 0
den = int(1e9 + 7)
for i in range(len(a)):
    for j in range(i + 1, len(a)):
        ans = (ans + a[i] * a[j]) % den

print(ans)

### FIXED CODE ###

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

ans = 0
den = int(1e9 + 7)
sum_a = [0 for i in range(len(a))]
sum_a[-1] = a[-1]
for i in range(len(a) - 1, 1, -1):
    sum_a[i - 1] = sum_a[i] + a[i - 1]
for i in range(len(a) - 1):
    ans = (ans + a[i] * sum_a[i + 1]) % den

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


h, w, m = map(int, input().split())

hw_map = [[0 for i in range(w)] for j in range(h)]
h_bomb_list = [0 for i in range(h)]
w_bomb_list = [0 for i in range(w)]

for i in range(m):
  bh, bw = map(int, input().split())
  hw_map[bh-1][bw-1] = 1
  h_bomb_list[bh-1] += 1
  w_bomb_list[bw-1] += 1
  

h_max = max(h_bomb_list)
h_argmax = max(zip(h_bomb_list, range(len(h_bomb_list))))[1]
w_max = max([w_bomb_list[i] - hw_map[h_argmax][i] for i in range(w)])
print(int(h_max+w_max))



### FIXED CODE ###


h, w, m = map(int, input().split())

h_b_list = [0 for i in range(h)]
w_b_list = [0 for i in range(w)]

targets = set()
for i in range(m):
  bh, bw = map(int, input().split())
  targets.add((bh, bw))
  h_b_list[bh-1] += 1
  w_b_list[bw-1] += 1
  
h_max = max(h_b_list)
w_max = max(w_b_list)

h_cans = []
w_cans = []
for i in range(h):
  if h_b_list[i] == h_max:
    h_cans.append(i)
    
for i in range(w):
  if w_b_list[i] == w_max:
    w_cans.append(i)

for hi in h_cans:
  for wi in w_cans:
    if (hi+1, wi+1) not in targets:
      print(h_max+w_max)
      exit()
else:
  print(h_max+w_max-1)
### BUGGY CODE ###

H,N = map(int,input().split())
MAXH = H+1
DP = [float("inf")]*MAXH
DP[0] = 0
a = [0]*N
b = [0]*N
for i in range(N):
  a[i],b[i] = map(int,input().split())
for i in range(MAXH):
  if DP[i] == float("inf"):
    continue    
  for j in range(N):
        DP[min(i+a[j],H)] = min(DP[min(i+a[j],H)],DP[i]+b[j])
print(DP[H])


### FIXED CODE ###

H,N = map(int,input().split())
MAXH = H+1
DP = [float("inf")]*MAXH
DP[0] = 0
a = [0]*N
b = [0]*N
for i in range(N):
  a[i],b[i] = map(int,input().split())
for i in range(MAXH):
  if DP[i] == float("inf"):
    continue    
  for j in range(N):
        DP[min(i+a[j],H)] = min(DP[min(i+a[j],H)],DP[i]+b[j])
print(DP[H])
### BUGGY CODE ###

from collections import deque
h,w = map(int,input().split())
grid = [list(input()) for i in range(h)]
que = deque([])
d = [[float('inf')]*w for i in range(h)]
for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            d[i][j] = 0
            que.append([i,j])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
ans = 0
while que:
    [px,py] = que.popleft()
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0<=nx<h and 0<=ny<w and grid[nx][ny] == '.' and d[nx][ny] == float('inf'):
            d[nx][ny] = d[px][py] + 1
            ans = d[nx][ny]
            que.append([nx,ny])
print(ans)


### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
a = []
d = []
que = deque()
for i in range(h):
    a.append(list(input()))
    d.append([1e100]*w)
    for j in range(w):
        if a[i][j] == '#':
            que.append([i,j])
            d[i][j] = 0
di = [-1,0,1,0]
dj = [0,1,0,-1]
ans = 0

while que:
    i,j = que.popleft()
    for k in range(4):
        ni = i + di[k]
        nj = j + dj[k]
        if 0 <= ni < h and 0 <= nj < w and d[ni][nj] == 1e100:
            d[ni][nj] = d[i][j] + 1
            ans = max(ans, d[ni][nj])
            que.append([ni,nj])
print(ans)