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

#ABC143-D:二分探索
n=int(input())
l=list(map(int,input().split()))
l=sorted(l,reverse=True)
ans=0
#print(l)
for i in range(n-2):
    for j in range(i+1,n-1):
        b=l[i]
        c=l[j]

        #二分探索
        ok=j
        ng=n
        while ng-ok>1:
            mid=(ok+ng)//2
            if l[mid]>b-c:
                #b>=cはわかってる
                ok=mid

            else:
                ng=mid

        ans+=ok-j
print(ans)

### FIXED CODE ###

#ABC143-D
n=int(input())
l=list(map(int,input().split()))
l=sorted(l,reverse=True)
ans=0
#print(l)
for i in range(n-2):
    for j in range(i+1,n-1):
        b=l[i]
        c=l[j]

        #二分探索
        ok=j
        ng=n
        while ng-ok>1:
            mid=(ok+ng)//2
            if l[mid]>b-c:
                #b>=cはわかってる
                ok=mid

            else:
                ng=mid

        ans+=ok-j
print(ans)
### BUGGY CODE ###

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

MAX = 10**9 + 7

def pow_mod_p(n, k, p):
  x = 1
  while k:
    if k % 2 == 1:
      x *= n
      x %= p
    n **= 2
    n %= p
    k >>= 1
  return x

def comb_mod_p(n, k, p):
  x = 1
  for ik in range(k):
    x *= ((n-ik) * pow_mod_p(ik+1, p-2, p))
    x %= p
  return x

def main():
  n, k = map(int, input().strip().split())
  for i in range(1,k+1):
    print((comb_mod_p(n-k+1, i, MAX) * comb_mod_p(k-1, i-1, MAX)) % MAX)

if __name__=='__main__':
  main()



### FIXED CODE ###

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

MAX = 10**9 + 7

def pow_mod_p(n, k, p):
  x = 1
  while k:
    if k % 2 == 1:
      x *= n
      x %= p
    n **= 2
    n %= p
    k >>= 1
  return x

def comb_mod_p(n, k, p):
  x = 1
  for ik in range(k):
    x *= ((n-ik) * pow_mod_p(ik+1, p-2, p))
    x %= p
  return x

def main():
  n, k = map(int, input().strip().split())
  a, b = comb_mod_p(n-k+1, 1, MAX), comb_mod_p(k-1, 1-1, MAX)
  for i in range(1,k+1):
    if i != 1:
      a = (a * (n-k+1-(i-1))) * pow_mod_p(i, MAX-2, MAX)
      b = (b * (k-1-((i-1)-1))) * pow_mod_p(i-1, MAX-2, MAX)
    print((a * b) % MAX)

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

s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
x = 1
for si in reversed(s):
  r += si*x
  r %= 2019
  d[r] += 1
  x *= 10
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)


### FIXED CODE ###

s = list(map(int,input()))
d = [0 for _ in range(2019)]
r = 0
x = 1
for si in reversed(s):
  r += si*x
  r %= 2019
  d[r] += 1
  x *= 10
  x %= 2019
ans = d[0]
for v in d:
  if v >= 2:
    ans += v*(v-1)//2
print(ans)
### BUGGY CODE ###

import math
a, b, n = map(int, input().split())
def f(n):
    return math.floor(a*n/b) - a*math.floor(n/b)
ans = f(n)
for x in range(b-1, n+1, b):
    ans = max(ans, f(x))
print(ans)

### FIXED CODE ###

from math import floor
a, b, n = map(int, input().split())
def f(x):
    return floor(a*x/b) - a*floor(x/b)
print(f(min(n, b-1)))
### BUGGY CODE ###

import sys
from heapq import heappop as hpp, heappush as hp

readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))

geta = 10**6        
Q = [-(B[i]*geta+i) for i in range(N)]
Q.sort()

ans = 0
cnt = 0
inf = 10**9+7
while cnt < N:
    b, idx = divmod(-hpp(Q), geta)
    bsec = Q[0]
    bsec = (-bsec)//geta
    a = A[idx]
    if b < a:
        ans = -1
        break
    bside = B[(idx+1)%N] + B[(idx-1)%N]
    kb = (1+(b-bsec)//bside)
    ka = (b-a)//bside
    k = min(ka, kb)
    B[idx] -= k*bside
    ans += k
    if B[idx] == a:
        cnt += 1
        hp(Q, inf*geta)
    elif k == 0:
        ans = -1
        break
    else:
        hp(Q, -(B[idx]*geta+idx))
print(ans)

### FIXED CODE ###

import sys
from heapq import heappop as hpp, heappush as hp

readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))

geta = 10**6        
Q = [-(B[i]*geta+i) for i in range(N)] + [0]
Q.sort()

ans = 0
cnt = 0
inf = 10**9+7
while cnt < N:
    b, idx = divmod(-hpp(Q), geta)
    a = A[idx]
    if b < a:
        ans = -1
        break
    bside = B[(idx+1)%N] + B[(idx-1)%N]
    kb = 1+(b-bside)//bside
    ka = (b-a)//bside
    k = min(ka, kb)
    B[idx] -= k*bside
    ans += k
    if B[idx] == a:
        cnt += 1
    elif k == 0:
        ans = -1
        break
    else:
        hp(Q, -(B[idx]*geta+idx))
print(ans)
### BUGGY CODE ###

n = int(input())
a_ = list(map(int, input().split()))
m = min(a_)
idx = a_.index(m)
a = a_[idx:] + a_[:idx]
for i in range(a[0] + 1):
    result = [0] * (n + 1)
    result[0] = i
    for j in range(1, n + 1):
        result[j] = a[j - 1] - result[j - 1]
    if result[0] == result[n]:
        result.pop()
        rans = result[-idx:] + result[:-idx]
        ans = [n*2 for n in rans]
        print(" ".join(map(str, ans)))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = [0] * n
sa = sum(a)
sa2 = sum(a[::2]) * 2
a.append(a[0])
ans[0] = sa2 - sa

for i in range(1, n):
    ans[i] = a[i - 1] * 2 - ans[i - 1]

print(' '.join(map(str, ans)))
### BUGGY CODE ###

import itertools

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

hmin = 10**18

c = itertools.combinations(h,K)

for v in c:
    hmin = min(max(v)-min(v),hmin)
print(hmin)

### FIXED CODE ###

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

print(min(h[i+K-1]-h[i] for i in range(N-K+1)))
### BUGGY CODE ###

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

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

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

### FIXED CODE ###

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

ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

from functools import reduce
n = input()
li = list(map(int, input().split()))
a = reduce((lambda x, y: x * y), li)
if a > 10**18:
    print(-1)
else:
    print(a)

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)
### BUGGY CODE ###

N,M=map(int,input().split())
e=[[0]*N for i in range(N)]

for _ in range(M):
  a,b = map(int,input().split())
  a,b = a-1, b-1
  e[a][b]=1
  e[b][a]=1

end_q=[]
def conn(s):
  q=[s]
  end_q.append(s)
  an=0
  while len(q)>0:
    qq=q.pop(0)
    an+=1
    for i in range(N):
      if e[qq][i]==1 and (i not in end_q):
        q.append(i)
        end_q.append(i)
  return an
ans=0
for a in range(N):
  if a in end_q:
    continue
  else:
    ans=max(ans,conn(a))
print(ans)

### FIXED CODE ###

#Union-Find木の実装
from collections import Counter
N,M=map(int,input().split())

#初期化
par=[i for i in range(N)]#親の要素(par[x]=xのときxは木の根)
rank=[0]*N#木の深さ

#木の根を求める
def find(x):
  #xが根だった場合xをそのまま返す
  if par[x] == x:
    return x
  else:
    #根が出るまで再帰する
    par[x] = find(par[x])
    return par[x]

#xとyの属する集合を併合
def unite(x,y):
  x=find(x)#xの根
  y=find(y)#yの根
  #根が同じなら何もしない
  if x == y:
    return
  #もし根の深さがyの方が深いなら
  if rank[x] < rank[y]:
    par[x] = y#yを根にする
  else:
    par[y] = x#xを根にする
    if rank[x] == rank[y]:
      rank[x]+=1

#xとyが同じ集合に属するか否か
#def same(x,y):
  #return find(x)==find(y)

for _ in range(M):
  a,b = map(int,input().split())
  a,b = a-1, b-1
  unite(a,b)

for i in range(N):
  find(i)
c=Counter(par)
c=c.most_common()[0][1]
print(c)
### BUGGY CODE ###

from sys import stdin
import bisect
n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]
a.sort()
sum = 0
for i in range(m):
    harf = a[n-1] // 2
    del a[n-1]
    bisect.insort_left(a, harf)
for i in range(n):
    sum += a[i]
print(sum)


### FIXED CODE ###

from sys import stdin
import heapq
n, m = [int(x) for x in stdin.readline().rstrip().split()]
a = [int(x) for x in stdin.readline().rstrip().split()]
a = [-1 * x for x in a]
heapq.heapify(a)
for i in range(m):
    harf = heapq.heappop(a)
    harf = ((harf*(-1))//2)*(-1)
    heapq.heappush(a,harf)
print(sum(a)*(-1))
### BUGGY CODE ###

n=int(input())
ans=1
for i in range(1,n+1):
  ans*=i
  
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
ans=1
for i in range(2,n+1):
  ans=(ans*i)%(10**9+7)
  
print(ans)
### BUGGY CODE ###

import math
import sys

n, m = map(int, input().split())
a_list = [None] * (m + 2)
a_list[0] = -1
for i in range(m):
    a_list[i+1] = int(input())
a_list[-1] = n + 1

fact_memo = dict()
def fact(n):
    if n in fact_memo.keys():
        return fact_memo[n]
    f = math.factorial(n)
    fact_memo[n] = f
    return f

memo = dict()
ans = 1
cur = a_list[0]
for i, a in enumerate(a_list):
    if i == 0:
        continue
    sub = a - cur - 1
    cur = a
    if sub <= 2:
        if sub == 0:
            print(0)
            sys.exit()
        continue
    sub -= 1
    if sub in memo.keys():
        ans *= memo[sub]
        continue
    count = 0
    for j in range(sub // 2 + 1):
        count += fact(sub - j) // fact(j) // fact(sub - j * 2)
    memo[sub] = count
    ans *= count
print(ans % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)
readline = sys.stdin.readline

N, M = map(int, readline().split())
ans = [0] * (N + 2)
ans[0] = 1
for _ in range(M):
    a = int(readline())
    ans[a] = -1

for i in range(1, N + 1):
    if ans[i] == -1:
        continue
    a1 = max(ans[i - 2], 0)
    a2 = max(ans[i - 1], 0)
    ans[i] = a1 + a2

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

n = int(input())
p = [int(i) for i in input().split()]

score = 1
for i in range(1,n):
  if min(p[:i]) >= p[i]:
    score += 1
    
print(score)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]

score = 1
m = p[0]
for i in range(1,n):
  m = min(m, p[i-1])
  if m >= p[i]:
    score += 1
    
print(score)
### BUGGY CODE ###

k=int(input())
if k%2==0:
    print(-1)
    exit()
count=1
while True:
    if int('7'*count)%k==0:
        print(count)
        break
    count+=len(str(k))

### FIXED CODE ###

k=int(input())
if k%2==0 or k%5==0:
    print(-1)
    exit()
a=0
for i in range(k):
    a=(a*10+7)%k
    if a==0:
        print(i+1)
        exit()
### BUGGY CODE ###

from collections import Counter
from copy import deepcopy

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    a_c= Counter(A)
    values = a_c.values()
    val_cnt = Counter(values)
    cnt = 0
    for a in A:
        a_c_c = deepcopy(a_c)
        val_cnt_c = deepcopy(val_cnt)
        val_cnt_c[a_c_c[a]] -= 1
        val_cnt_c[a_c_c[a]-1] += 1
        cnt = {int(k*(k-1)/2*v)  if k > 1 else 0 for k, v in val_cnt_c.items()}
        print(sum(cnt))
    
if __name__ == '__main__':
    main()
    

### FIXED CODE ###

from collections import Counter
 
def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    a_c = Counter(A)
    res = [int(v*(v-1)/2) for v in a_c.values()]
    cnt = sum(res)
    for a in A:
        ans = (cnt - (a_c[a]-1))
        print(ans)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
N, M = map(int, input().split())
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]
A.sort()
B.sort()
table = [[0] * M for _ in range(N)]
i = N
j = M
ans = 1
for n in range(N*M, 0, -1):
    if A[i-1] == n and B[j-1] == n:
        i -= 1
        j -= 1
        if table[i][j] > 0:
            print(0)
            sys.exit()
        table[i][j] = n
    elif A[i-1] == n:
        i -= 1
        ans *= M - j
    elif B[j-1] == n:
        j -= 1
        ans *= N - i
    else:
        ans *= (N - i) * (M - j) - (N*M - n)
print(ans % 1000000007)


### FIXED CODE ###

import sys
mod = 1000000007
N, M = map(int, input().split())
A = [int(s) for s in input().split()]
B = [int(s) for s in input().split()]
A.sort()
B.sort()
i = N
j = M
ans = 1
for n in range(N*M, 0, -1):
    if A[i-1] == n and B[j-1] == n:
        i -= 1
        j -= 1
    elif A[i-1] == n:
        i -= 1
        ans *= M - j
        ans %= mod
    elif B[j-1] == n:
        j -= 1
        ans *= N - i
        ans %= mod
    else:
        ans *= ((N - i) * (M - j) - (N*M - n)) % mod
        ans %= mod
print(ans % mod)
### BUGGY CODE ###

s = input()
q = int(input())
ls = [input().split() for _ in range(q)]

for t in ls:
    if t[0] == '1':
        s = s[::-1]
    elif t[0] == '2':
        if t[1] == '1':
            s = t[2] + s
        elif t[1] == '2':
            s = s + t[2]
    
print(s)

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
ls = [input().split() for _ in range(q)]

ans = deque(s)
cnt = 0

for t in ls:
    if t[0] == '1':
        cnt += 1
    elif t[0] == '2':
        if cnt % 2 == 0:
            if t[1] == '1':
                ans.appendleft(t[2])
            elif t[1] == '2':
                ans.append(t[2])
        elif cnt % 2 == 1:
            if t[1] == '1':
                ans.append(t[2])
            elif t[1] == '2':
                ans.appendleft(t[2])

if cnt % 2 == 0:
    print("".join(ans))
elif cnt % 2 == 1:
    ans.reverse()
    print("".join(ans))
### BUGGY CODE ###

import sys
#import numpy as np
import math
from fractions import Fraction
import itertools

input=sys.stdin.readline
n=int(input())
a=[int(input()) for _ in range(n)]
print(max(a[1:]))
for i in range(1,n-1):
    print(max(max(a[:i]),max(a[i+1:])))
    
print(max(a[:n-1]))

### FIXED CODE ###

import sys
#import numpy as np
import math
from fractions import Fraction
import itertools

input=sys.stdin.readline
n=int(input())
a=[int(input()) for _ in range(n)]
l=[0]*n
r=[0]*n
l[0]=a[0]
r[0]=a[-1]
for i in range(1,n):
    if a[i]>l[i-1]:
        l[i]=a[i]
    else:
        l[i]=l[i-1]
    if a[n-1-i]>r[i-1]:
        r[i]=a[n-1-i]
    else:
        r[i]=r[i-1]
print(r[n-2])
for i in range(1,n-1):
    print(max(l[i-1],r[n-i-2]))
print(l[n-2])
### BUGGY CODE ###

s = input()
sc = s[::-1]
n = int(input())
l = [list(input().split()) for i in range(n)]

for i in range(n):
    if l[i][0] == '1':
        save = s
        s = sc
        sc = save
    elif l[i][1] == '1':
        s = l[i][2] + s
        sc += l[i][2]
    else:
        s += l[i][2]
        sc = l[i][2] + sc

print(s)

### FIXED CODE ###

import copy
from collections import deque
s = deque(input())
sc = copy.deepcopy(s) 
sc.reverse()
n = int(input())
l = [list(input().split()) for i in range(n)]

for i in range(n):
    if l[i][0] == '1':
        save = s
        s = sc
        sc = save
    elif l[i][1] == '1':
        s.appendleft(l[i][2])
        sc.append(l[i][2])
        #s = l[i][2] + s
        #sc += l[i][2]
    else:
        s.append(l[i][2])
        sc.appendleft(l[i][2])
        #s += l[i][2]
        #sc = l[i][2] + sc

print(''.join(s))
### BUGGY CODE ###

l=[2658,3]
d=[2,4,5]
d_bar=[]
for m in range(10):
    if m not in d:
        d_bar.append(m) 
d_bar.sort()
n=[int(k) for k in str(l[0])]

for i in range(len(n)):
    dig1=''
    dig2=0
    for j in range(l[1]):
        p=dig1.join(str(d_bar[j]))
        if int(p)>l[0]:
          dig2=dig2+int(dig1)*l[1]**(l[0]-i)
          break
        dig1=p     
dig2=dig2+1
r=int(dig1)
q=int(dig1)
R=[]
while q!=0 or q!=1:
    q=q/l[1]
    r=q%l[1]
    R.insert(0,r)
s=''
for t in range(len(R)):
    s=s+str(R[t])
print(int(s))




### FIXED CODE ###

L = sorted(map(int, input().split()))
 
ans = 'YES' if L == [5, 5, 7] else 'NO'
print(ans)
### BUGGY CODE ###

# D
import numpy as np
N = int(input())
X = np.zeros(N, dtype=int)
Y = np.zeros(N, dtype=int)

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

# edges
X_s = np.argsort(X)
Y_s = np.argsort(Y)

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(min(abs(X[X_s[i+1]] - X[X_s[i]]), abs(Y[X_s[i+1]] - Y[X_s[i]])))
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(min(abs(X[Y_s[i+1]] - X[Y_s[i]]), abs(Y[Y_s[i+1]] - Y[Y_s[i]])))
    
# sort edges
sel = np.argsort(np.array(edge_weight))

# union find tree
uf = dict()
for i in range(N):
    uf[i] = [i, 0]

res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    # find union
    gr_m = m
    gr_n = n
    dep_m = 0
    dep_n = 0
    while gr_m != uf[gr_m][0]:
        gr_m = uf[gr_m][0]
        dep_m += 1
    uf[gr_m][1] = max(uf[gr_m][1], dep_m)
    uf[m] = [gr_m, dep_m]
    while gr_n != uf[gr_n][0]:
        gr_n = uf[gr_n][0]
        dep_n += 1
    uf[gr_n][1] = max(uf[gr_n][1], dep_n)
    uf[n] = [gr_n, dep_n]
    if gr_m == gr_n:
        pass
    else:
        res += edge_weight[s]
        if dep_m > dep_n:
            uf[gr_n] = [gr_m, dep_m]
        elif dep_m > dep_n:
            uf[gr_n] = [gr_m, dep_m+1]
        else:
            uf[gr_m] = [gr_n, dep_n]
print(res)

### FIXED CODE ###

# D
import numpy as np
N = int(input())
X = []
Y = []

for i in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

# edges
X_s = np.argsort(np.array(X))
Y_s = np.argsort(np.array(Y))

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(X[X_s[i+1]] - X[X_s[i]])
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(Y[Y_s[i+1]] - Y[Y_s[i]])
    
# sort edges
sel = np.argsort(np.array(edge_weight))

# union find tree
uf = np.arange(N)


res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    # find union
    gr_m = m
    gr_m_list = []
    gr_n = n
    gr_n_list = []
    while gr_m != uf[gr_m]:
        gr_m_list.append(gr_m)
        gr_m = uf[gr_m]
    for m_ in gr_m_list:
        uf[m_] = gr_m
        
    while gr_n != uf[gr_n]:
        gr_n_list.append(gr_n)
        gr_n = uf[gr_n]
    for n_ in gr_n_list:
        uf[n_] = gr_n
        
    if gr_m == gr_n:
        pass
    else:
        res += edge_weight[s]
        uf[gr_n] = gr_m
print(res)
### BUGGY CODE ###

import collections

N = int(input())

even = collections.defaultdict(lambda: 0)
odd = collections.defaultdict(lambda: 0)

for i, a in enumerate(map(int, input().split())):
    if i % 2 == 0:
        even[a] += 1
    else:
        odd[a] += 1

if len(even.keys()) == 1 and len(odd.keys()) == 1 and list(even.keys())[0] == list(odd.keys())[0]:
    print(N // 2)
else:
    m = 0
    for e_k, e_v in even.items():
        for o_k, o_v in odd.items():
            if e_k == o_k:
                continue
            m = max(m, e_v + o_v)

    print(N - m)


### FIXED CODE ###

import collections

N = int(input())

even = collections.defaultdict(lambda: 0)
odd = collections.defaultdict(lambda: 0)

for i, a in enumerate(map(int, input().split())):
    if i % 2 == 0:
        even[a] += 1
    else:
        odd[a] += 1

if len(even.keys()) == 1 and len(odd.keys()) == 1 and list(even.keys())[0] == list(odd.keys())[0]:
    print(N // 2)
else:
    m = 0
    for e_k, e_v in sorted(even.items(), key=lambda x: x[1], reverse=True)[:2]:
        for o_k, o_v in sorted(odd.items(), key=lambda x: x[1], reverse=True)[:2]:
            if e_k == o_k:
                continue
            m = max(m, e_v + o_v)

    print(N - m)
### BUGGY CODE ###

import sys

t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())

if t1*a1+t2*a2 == t1*b1+t2*b2:
    print("infinity")
    sys.exit()

a, b = 0, 0
key = 0
ans = 0
while True:
    key = ans
    while True:
        a_past, b_past = a, b
        a += a1*t1
        b += b1*t1
        if a_past == b_past:
            break
        if (a_past-b_past)*(a-b) <= 0:
            ans += 1
        break
    while True:
        a_past, b_past = a, b
        a += a2*t2
        b += b2*t2
        if a_past == b_past:
            break
        if (a_past-b_past)*(a-b) <= 0:
            ans += 1
        break
    if key == ans:
        break
print(ans)

### FIXED CODE ###

import sys

t1, t2 = map(int, input().split())
a1, a2 = map(int, input().split())
b1, b2 = map(int, input().split())

if (a1-b1)*t1+(a2-b2)*t2 == 0:
  print("infinity")
  sys.exit()

e1 = (a1-b1)*t1
e2 = e1 + (a2-b2)*t2

if e1*e2 > 0:
  print(0)
  sys.exit()

e1, e2 = abs(e1), abs(e2)

if e1%e2:
  print(1+2*(e1//e2))
else:
  print(2*(e1//e2))
### BUGGY CODE ###


def is_triangle(a, b, c):
    if a >= b + c:
        return False

    if b >= a + c:
        return False

    if c >= a + b:
        return False

    return True


def main():
    N = int(input())
    L = list([int(x) for x in input().split()])

    L.sort(reverse=True)

    count = 0
    for index, a in enumerate(L):
        if index + 2 == N:
            break

        for b_i in range(index+1, N):
            b = L[b_i]
            c_i = 1

            while not is_triangle(a, b, L[-c_i]):
                if c_i + b_i == N:
                    break
                c_i += 1

            count += (N - b_i - c_i)

    print(count)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def is_triangle(a, b, c):
    if a >= b + c:
        return False

    if b >= a + c:
        return False

    if c >= a + b:
        return False

    return True


def main():
    N = int(input())
    L = list([int(x) for x in input().split()])

    L.sort()

    count = 0
    for index, a in enumerate(L):
        if index + 2 == N:
            break

        for b_i in range(index+1, N):
            b = L[b_i]
            c = 1

            while not is_triangle(a, b, L[-c]):
                c += 1

            count += (N - b_i - c)

    print(count)


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

def clear_maze(sx, sy, gx, gy, maze):

    INF = 100000000

    distance = [[INF for i in range(W)] for j in range(H)]
    #    distance = [[None]*field_x_length]*field_y_length

    def bfs():
        queue = []

        queue.insert(0, (sx, sy))

        distance[sy][sx] = 0

        while len(queue):
            x, y = queue.pop()

            if x == gx and y == gy:
                break

            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]

                if (0 <= nx and nx < W and 0 <= ny and ny < H and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (nx, ny))
                    distance[ny][nx] = distance[y][x] + 1


        return distance[gy][gx]

    return bfs()


H,W = (int(x) for x in input().split())

maze = ['']*H
max_distance = 0
for i in range(H):
  maze[i] = list(input())
  
for sy in range(H):
  for sx in range(W):
    for gy in range(H):
      for gx in range(W):
        if sx == gx and sy == gy:
          continue
        tmp_s = maze[sy][sx]
        tmp_g = maze[gy][gx]
        maze[sy][sx] = 'S'
        maze[gy][gx] = 'G'
        
        max_distance = max(max_distance,clear_maze(sx, sy, gx, gy, maze))
        maze[sy][sx] = tmp_s
        maze[gy][gx] = tmp_g
        
print(max_distance)
    

    

### FIXED CODE ###

from collections import deque
import math
import copy
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
def bfs(maze,h,w,sx,sy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    m = 0                   
    for l in maze:
      li = [i for i in l if i != '#' and i < 1000000]
      if len(li) > 0:
        m = max(m,max(li))
    return m
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '#':
      continue
    copymaze = copy.deepcopy(maze)
    res = bfs(copymaze,H,W,sj,si)
    max_dist = max(max_dist,res)
print(max_dist)