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

from collections import deque
from itertools import product

def solve():
    H, W = map(int, input().split())

    l = []
    for _ in range(H):
        l.append([0 if s=="." else 1 for s in input()])

    ans = 0

    for sh,sw,gh,gw in product(range(H),range(W),range(H),range(W)):
        if gw==sw and gh==sh:
            continue
        if l[gh][gw] or l[sh][sw]:
            continue

        q = deque([(sh, sw)])
        dist = [[10**12]*W for _ in range(H)]
        dist[sh][sw] = 0
        while q:
            h, w = q.popleft()
            for h1, w1 in [(h+1, w), (h, w+1), (h-1, w), (h, w-1)]:
                if not (0<=h1<H and 0<=w1<W):continue
                if l[h1][w1]:continue
                if dist[h1][w1] > dist[h][w] + 1:
                    dist[h1][w1] = dist[h][w] + 1
                    q.append((h1, w1))
        ans = max(ans, dist[gh][gw])
        
    print(ans)

solve()

### FIXED CODE ###

H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))
### BUGGY CODE ###

N = int(input())
from collections import Counter
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
h = []
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    heappush(h,(-ca[i]-cb[i],i))
lis = [[] for _ in range(N+1)]
while len(h):
  cnt, n = heappop(h)
  cnt2, n2 = heappop(h)
  if ca[n]>0:
    ca[n] -= 1
    cnt += 1
    lists = []
    while cb[n2]==0:
      lists.append((cnt2,n2))
      cnt2, n2 = heappop(h)
    for cnt3, n3 in lists:
      heappush(h,(cnt3,n3))
    cb[n2] -= 1
    cnt2 += 1
    lis[n].append(n2)
    if cnt<0:
      heappush(h,(cnt,n))
    if cnt2<0:
      heappush(h,(cnt2,n2))
  else:
    cb[n] -= 1
    cnt += 1
    lists = []
    while ca[n2]==0:
      lists.append((cnt2,n2))
      cnt2, n2 = heappop(h)
    for cnt3, n3 in lists:
      heappush(h,(cnt3,n3))
    ca[n2] -= 1
    cnt2 += 1
    lis[n2].append(n)
    if cnt<0:
      heappush(h,(cnt,n))
    if cnt2<0:
      heappush(h,(cnt2,n2))
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)


### FIXED CODE ###

N = int(input())
from collections import Counter
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
cnts = [set() for _ in range(N+1)]
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    cnts[ca[i]+cb[i]].add(i)

def get_any(counts,r):
  for k in counts.keys():
    if counts[k]>0 and k!=r:
      return k

def update_cnt(cnt_,r):
  cnt_[r] -= 1
  if cnt_[r]==0:
    del cnt_[r]

lis = [[] for _ in range(N+1)]
for i in range(N,0,-1):
  if len(cnts[i])==2:
    p,q = cnts[i]
    for j in range(ca[p]):
      lis[p].append(q)
    for j in range(ca[q]):
      lis[q].append(p)
    break
  elif len(cnts[i])==1:
    p, = cnts[i]
    for j in range(ca[p]):
      q = get_any(cb,p)
      update_cnt(cb,q)
      lis[p].append(q)
    for j in range(cb[p]):
      q = get_any(ca,p)
      update_cnt(ca,q)
      lis[q].append(p)
    break
  else:
    p = get_any(ca,-1)
    q = get_any(cb,p)
    lis[p].append(q)
    cnts[ca[p]+cb[p]].remove(p)
    cnts[ca[q]+cb[q]].remove(q)
    update_cnt(ca,p)
    update_cnt(cb,q)
    cnts[ca[p]+cb[p]].add(p)
    cnts[ca[q]+cb[q]].add(q)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)
### BUGGY CODE ###

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


def price(x):
    return x // 2


for i in range(m):
    x = max(a)
    y = a.index(x)
    a[y] = price(x)

print(sum(a))


### FIXED CODE ###

import heapq
n, m = map(int, input().split())
price = list(map(lambda x: int(x) * (-1), input().split()))

heapq.heapify(price)
for _ in range(m):
    max_price = -heapq.heappop(price)
    heapq.heappush(price, -(max_price//2))

ans = -sum(price)
print(ans)
### BUGGY CODE ###

import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    N = int(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    for n in range(1,N+1):
        ans = 0
        for x in range(1,int((n//3)**0.5)+1):
            for y in range(1,int((n//3)**0.5)+1):
                pre = x**2 + y**2 + x*y
                uu = n-pre
                if uu<0:
                    break
                for z in range(1,int(uu**0.5)+1):
                    if z*(z+x+y)==uu:
                        if len(set([x,y,z])) == 1:
                            ans = 1
                            break
                        elif len(set([x,y,z])) == 2:
                            ans = 3
                            break
                        else:
                            ans = 6
                            break
        print(ans)



if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    N = int(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zer
    ans = [0]*N
    for x in range(1,int(N**0.5)+1):
        for y in range(1,int(N**0.5)+1):
            for z in range(1,int(N**0.5)+1):
                a = x**2 + y**2 + z**2 +x*y + y*z + z*x
                if a > N:
                    break
                ans[a-1] += 1

    for i in range(N):
        print(ans[i])



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

S = str(input())
ans = 0
for i in range(len(S)+1):
    for j in range(i+4,len(S)+1):
        if(int(S[i:j]) % 2019 == 0):
            ans += 1
print(ans)

### FIXED CODE ###

S = str(input())
# 余りのリスト
counts = [0] * 2019
n, d = 0, 1

for s in S[::-1]:
    n += int(s) * d
    d *= 10
    n %= 2019
    d %= 2019
    counts[n] += 1
ans = counts[0]
for count in counts:
    ans += count * (count - 1) // 2
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

res = 0
for i in range(N // R + 1):
    for j in range(N // G + 1):
        b = N - (i * R + j * G)
        if b >= 0 and b % B == 0:
            res += 1
print(res)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

res = 0
for i in range(N // R + 1):
    for j in range(N // G + 1):
        b = N - (i * R + j * G)
        if b >= 0 and b % B == 0:
            res += 1
print(res)
### BUGGY CODE ###

import sys
n=int(input())
a=list(map(int,input().split()))
s=0
b=0
while 1:
    t=True
    for i in range(len(a)):
        if a[i]!=i+1:
            t=False
            break
    if t:
        print(b)
        sys.exit()
    if a[s]!=s+1:
        del a[s]
        b+=1
        if len(a)==0:
            print(-1)
            sys.exit()
    else:
        s+=1

### FIXED CODE ###

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

purged_data = [] #purge : [動詞]〜を粛清する
tmp = a[0] - 1
s=1
for i, e in enumerate(a):
    if e==s:
        purged_data.append(e)
        tmp = e
        s+=1
for i in range(len(purged_data)):
    if purged_data[i]!=i+1:
        print(-1)
        sys.exit()
if len(purged_data)==0:
    print(-1)
    sys.exit()
print(len(a)-len(purged_data))
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())
    s = ["#" * (w + 2)]
    for _ in range(h):
        s.append("#" + input() + "#")
    s.append("#" * (w + 2))

    b = [[0] * (w + 2) for _ in range(h + 2)]
    for hi in range(h + 2):
        for wi in range(w + 2):
            if s[hi][wi] == ".":
                b[hi][wi] = 1

    u = [[0] * (w + 2) for _ in range(h + 2)]
    d = [[0] * (w + 2) for _ in range(h + 2)]
    l = [[0] * (w + 2) for _ in range(h + 2)]
    r = [[0] * (w + 2) for _ in range(h + 2)]

    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            if b[hi][wi]:
                u[hi][wi] = u[hi-1][wi] + 1
                l[hi][wi] = l[hi][wi-1] + 1

    for hi in range(h, 0, -1):
        for wi in range(w, 0, -1):
            if b[hi][wi]:
                d[hi][wi] = d[hi+1][wi] + 1
                r[hi][wi] = r[hi][wi+1] + 1

    ans = 0
    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            cnt = u[hi][wi] + d[hi][wi] + l[hi][wi] + r[hi][wi] - 3
            ans = max(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    h, w = map(int, input().split())
    s = [input() for _ in range(h)]

    m = [[0] + [0 if e == "#" else 1 for e in s[i]] + [0] for i in range(h)]
    m.append([0] * (w + 2))
    m.insert(0, [0] * (w + 2))

    m_t = [[m[i][j] for i in range(h+2)] for j in range(w+2)]

    lr = []
    for i in range(h + 2):
        sm = 0
        row = []
        for j in range(w + 2):
            if m[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        lr.append(row)

    ud = []
    for i in range(w + 2):
        sm = 0
        row = []
        for j in range(h + 2):
            if m_t[i][j]:
                sm += 1
            else:
                row += [sm] * sm + [0]
                sm = 0

        ud.append(row)

    ans = 0
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            sm = lr[i][j] + ud[j][i] - 1
            ans = max(ans, sm)

    print(ans)


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

import sys
sys.setrecursionlimit(10000000)
# N = 4
# ARR = [10, 30, 40, 20]

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

def calculate(n, arr):
    result = aaa(0, n - 1)
    print(result)


def aaa(currentPosition, endPosition, cost=0):
    if currentPosition == endPosition:
        return cost
    if currentPosition == (endPosition - 1):
        return aaa(endPosition, endPosition, cost + abs(ARR[endPosition] - ARR[currentPosition]))

    a1 = abs(ARR[currentPosition + 1] - ARR[currentPosition])
    a2 = abs(ARR[currentPosition + 2] - ARR[currentPosition])

    s1 = aaa(currentPosition + 1, endPosition, cost + a1)
    s2 = aaa(currentPosition + 2, endPosition, cost + a2)
    return min(s1, s2)

calculate(N, ARR)


### FIXED CODE ###

# N = 4
# HRR = [10, 30, 40, 20]
# N = 2
# HRR = [10, 10]

N = int(input())
HRR = list(map(int,input().split()))
result = []
for i in range(N):
    if i == 0:
        result.append(0)
    elif i == 1:
        s1 = result[i - 1] + abs(HRR[i] - HRR[i - 1])
        result.append(s1)
    else:
        s1 = result[i - 1] + abs(HRR[i] - HRR[i - 1])
        s2 = result[i - 2] + abs(HRR[i] - HRR[i - 2])
        result.append(min(s1, s2))

print(result[-1])
### BUGGY CODE ###

a, b, m = list(map(int, input().split()))
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
sum_list = []
list1 = []

for i in a_list:
    for j in b_list:
        list1.append(i + j)

for i in range(m):
    x, y, c = list(map(int, input().split()))
    sum = a_list[x - 1] + b_list[y - 1] - c
    sum_list.append(sum)

# print(list1)
# print(sum_list)
print(min(min(sum_list), min(list1)))

### FIXED CODE ###

a, b, m = list(map(int, input().split()))
a_list = list(map(int, input().split()))
b_list = list(map(int, input().split()))
sum_list = []

min_sum = min(a_list) + min(b_list)


for i in range(m):
    x, y, c = list(map(int, input().split()))
    sum = a_list[x - 1] + b_list[y - 1] - c
    sum_list.append(sum)

print(min(min(sum_list), min_sum))
### BUGGY CODE ###

L, A, B, M = map(int, raw_input().split())

# first i such that A + i*B has d digits.
# A + i*B >= 10^d
# i*B >= 10^d - A
# i >= 
# i = (10^d - A + (B-1))/B

def get_indices(d):
	i_start = (10**d - A + (B-1)) / B
	i_end = (10**(d+1) - A + (B-1)) / B
	i_start = max(0, i_start)
	i_end = max(0, i_end)
	i_start = min(L, i_start)
	i_end = min(L, i_end)
	return (d+1, i_start, i_end)
	
index_pairs = [get_indices(n) for n in xrange(0, 19)]

def get_chunk_value(num_digs, i_start, i_end):
	if i_start == i_end:
		return (0, 0)
	
	a = A + B*(i_end - 1)
	d = -B
	n = i_end - i_start
	r = 10 ** num_digs
	
	Mt = M*((1-r)**2)
	
	numerator = (1-r)*(a - (a + n*d)*pow(r, n, Mt)) + d*r*(1 - pow(r, n, Mt))
	numerator %= Mt
	assert numerator % (1-r)**2 == 0
	return (num_digs*(i_end-i_start), numerator/(1-r)**2)
	
	

# print index_pairs
chunk_values = [get_chunk_value(n, i_start, i_end) for n, i_start, i_end 
													in index_pairs]
# print chunk_values

ans = 0
digits_offset = 0
for num_digs, value in reversed(chunk_values):
	ans += value * pow(10, digits_offset)
	digits_offset += num_digs
	
ans %= M
print ans
	





### FIXED CODE ###

L, A, B, M = map(int, raw_input().split())

# first i such that A + i*B has d digits.
# A + i*B >= 10^d
# i*B >= 10^d - A
# i >= 
# i = (10^d - A + (B-1))/B

def get_indices(d):
	i_start = (10**d - A + (B-1)) / B
	i_end = (10**(d+1) - A + (B-1)) / B
	i_start = max(0, i_start)
	i_end = max(0, i_end)
	i_start = min(L, i_start)
	i_end = min(L, i_end)
	return (d+1, i_start, i_end)
	
index_pairs = [get_indices(n) for n in xrange(0, 19)]

def get_chunk_value(num_digs, i_start, i_end):
	if i_start == i_end:
		return (0, 0)
	
	a = A + B*(i_end - 1)
	d = -B
	n = i_end - i_start
	r = 10 ** num_digs
	
	Mt = M*((1-r)**2)
	
	numerator = (1-r)*(a - (a + n*d)*pow(r, n, Mt)) + d*r*(1 - pow(r, n, Mt))
	numerator %= Mt
	assert numerator % (1-r)**2 == 0
	return (num_digs*(i_end-i_start), numerator/(1-r)**2)
	
	

# print index_pairs
chunk_values = [get_chunk_value(n, i_start, i_end) for n, i_start, i_end 
													in index_pairs]
# print chunk_values

ans = 0
digits_offset = 0
for num_digs, value in reversed(chunk_values):
	ans += value * pow(10, digits_offset, M)
	digits_offset += num_digs
	
ans %= M
print ans
### BUGGY CODE ###

S = str(input())
K = int(input())

# Sのsubstring全列挙を行う
ans = []

for i in range(len(S)):
    for j in range(i+1, len(S)+1):
        ans.append(S[i:j])

ans = list(set(ans))
ans.sort()
print(ans[K-1])


### FIXED CODE ###

S = str(input())
K = int(input())

# Sのsubstring全列挙を行う
ans = []

for i in range(len(S)):
    for j in range(i+1, i+K+1):
        ans.append(S[i:j])

ans = list(set(ans))
ans.sort()

print(ans[K-1])
### BUGGY CODE ###

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

for i in range(m):
    a, b = map(int, input().split())
    ab = set([j for j in range(a,b+1)])
    n = n & ab
    if len(n) == 0:
        print(0)
        exit()

print(len(n))

### FIXED CODE ###

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

left = 1
right = n

for i in range(m):
    a, b = map(int, input().split())
    if a > left:
        left = a
    if b < right:
        right = b
    
    if left > right:
        print(0)
        exit()

print(right-left+1)
### BUGGY CODE ###

import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
for i in range(1, N):
    ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
    sum += ans//a
print(sum%(7+10**9))

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline
N = int(input())
list_A = list(map(int, input().split()))
ans = list_A[0]
sum = 0
for i in range(1, N):
  ans = ans * list_A[i] // fractions.gcd(ans, list_A[i])
for a in list_A:
  sum += ans//a
print(sum%(7+10**9))
### BUGGY CODE ###

n, k, l = map(int, input().split())


class UnionFind():
    def __init__(self, n):
        self.tree = [i for i in range(n)]

    def root(self, x):
        if(self.tree[x] == x):
            return x
        self.tree[x] = self.root(self.tree[x])
        return self.tree[x]  # 経路圧縮

    def same(self, x, y):  # xとyが同じ木に属するか
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if(x == y):
            return
        self.tree[x] = y


uf = UnionFind(n)
uf2 = UnionFind(n)

for _ in range(k):
    p, q = map(int, input().split())
    uf.unite(q-1, p-1)
for _ in range(l):
    r, s = map(int, input().split())
    uf2.unite(s-1, r-1)

table = [[0]*n for _ in range(n)]

for i in range(n):
    table[uf.root(i)][uf2.root(i)] += 1
for i in range(n):
    print(table[uf.root(i)][uf2.root(i)], end=' ')

exit(0)
for i, j in [(uf.root(i), uf2.root(i)) for i in range(n)]:
    table[i][j] += 1
for i, j in [(uf.root(i), uf2.root(i)) for i in range(n)]:
    print(table[i][j], end=' ')


exit(0)
for i in range(n):
    ans = 0
    for j in range(n):
        if uf.same(i, j) and uf2.same(i, j):
            ans += 1
    print(ans, end=' ')

### FIXED CODE ###

n, k, l = map(int, input().split())


class UnionFind():
    def __init__(self, n):
        self.tree = [i for i in range(n)]

    def root(self, x):
        if(self.tree[x] == x):
            return x
        self.tree[x] = self.root(self.tree[x])
        return self.tree[x]  # 経路圧縮

    def same(self, x, y):  # xとyが同じ木に属するか
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if(x == y):
            return
        self.tree[x] = y


uf = UnionFind(n)
uf2 = UnionFind(n)

for _ in range(k):
    p, q = map(int, input().split())
    uf.unite(q-1, p-1)
for _ in range(l):
    r, s = map(int, input().split())
    uf2.unite(s-1, r-1)

#table = [[0]*n for _ in range(n)]
table = dict()

for i in range(n):
    #table[uf.root(i)][uf2.root(i)] += 1
    table[(uf.root(i), uf2.root(i))] = table.get(
        (uf.root(i), uf2.root(i)), 0)+1
for i in range(n):
    print(table[(uf.root(i), uf2.root(i))], end=' ')

exit(0)
for i, j in [(uf.root(i), uf2.root(i)) for i in range(n)]:
    table[i][j] += 1
for i, j in [(uf.root(i), uf2.root(i)) for i in range(n)]:
    print(table[i][j], end=' ')


exit(0)
for i in range(n):
    ans = 0
    for j in range(n):
        if uf.same(i, j) and uf2.same(i, j):
            ans += 1
    print(ans, end=' ')
### BUGGY CODE ###

N = input()
N = int(N)


def chose(i,j):
    count=0
    for x in range(1,N+1):
        X=str(x)
        
        if int(X[0])==i and int(X[-1])==j:
            count+=1
    return count

score = 0
for i in range(10):
    for j in range(10):
        score += chose(i,j)*chose(j,i)
        
print(score)
        
    

### FIXED CODE ###

N = input()
N = int(N)

c=[[0 for i in range(10)] for j in range(10)]

c[0][0]
for x in range(1,N+1):
    X=str(x)
    c[int(X[0])][int(X[-1])]+=1

score = 0
for i in range(10):
    for j in range(10):
        score += c[i][j]*c[j][i]
        
print(score)
### BUGGY CODE ###

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i&(-i)
        return s

    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i&(-i)
            
left, right = 0, 10**9
geta = n+1
while right-left > 1:
    mid = (left+right)//2
    num = 0
    bit = BIT(2*n+1)
    sum_ = 0
    bit.add(sum_+geta, 1)
    for i in range(n):
        val = 1 if a[i] <= mid else -1
        sum_ += val
        num += bit.sum(sum_+geta-1)
        bit.add(sum_+geta, 1)

    if num > n*(n+1)//4:
        right = mid
    else:
        left = mid
print(right)


### FIXED CODE ###

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

a_sorted = sorted(set(a))+[10**18]
left, right = 0, len(a_sorted)-1

while right-left > 1:
    mid = (left+right)//2
    x = a_sorted[mid]

    count = [0]*(2*n+1)
    count[n+1] = 1
    i, accum, res = n+1, 1, 0

    for aa in a:
        if aa >= x:
            i += 1
            accum += count[i]
        else:
            accum -= count[i]
            i -= 1

        res += accum
        count[i] += 1
        accum += 1

    if res >= n*(n+1)//4:
        left = mid
    else:
        right = mid

print(a_sorted[left])
### BUGGY CODE ###

x = int(input())

for i in range(x):
    s = x - i**5
    if(s < 0):continue
    t = int(s ** 0.2)
    if(s == t**5):
        print(i,-t)
        exit()

### FIXED CODE ###

x = int(input())


for i in range(-1000,1000):
    s = x + pow(i,5)
    t = pow(s,0.2)
    if(t.imag == 0):
        t = int(t)
        if(pow(t,5) == s):
            print(t,i)
            exit()
### BUGGY CODE ###

n = int(input())
pp = list(map(int, input().split()))


def sub(pp):
	m = len(pp)
	ans = 0
	for i in range(m - 1):
		for j in range(i + 1, m):
			#print(i, j)
			ans += sorted(pp[i:(j + 1)], reverse = True)[1]
	return ans

def calc(a, b):
	if b - a < 1:
		return 0
	elif b - a == 1:
		return min(pp[b], pp[a])
	else:
		pn = sorted(pp[a:(b + 1)], reverse = True)
		f = pp.index(pn[0])
		s = pp.index(pn[1])
		if f > s:
			ans = calc(a, f - 1) + calc(s + 1, b) - calc(s + 1, f - 1) + pp[s] * ((s - a + 1) * (b - f + 1))
		else:
			ans = calc(a, s - 1) + calc(f + 1, b) - calc(f + 1, s - 1) + pp[s] * ((f - a + 1) * (b - s + 1))
		#print(a, b, f, s,  ans)
		return ans


#print(sub(pp))
print(calc(0, n - 1))

### FIXED CODE ###


def main():
	n = int(input())
	xx = list(map(int, input().split()))

	pp = [(xx[i], i + 1) for i in range(n)]
	pp.sort(key=lambda x: x[0])
	# print(xx)
	# print(pp)

	left = [0, 0] + [i + 1 for i in range(n)]
	right = [i + 1 for i in range(n)] + [n + 1, n + 1]
	ans = 0
	for i in range(n):

		ori_num, ori_ind = pp[i]
		l1 = left[ori_ind]
		l2 = left[l1]
		r1 = right[ori_ind]
		r2 = right[r1]

		# print("ori_num, ori_ind, l1, l2, r1, r2")
		# print(ori_num, ori_ind, l1, l2, r1, r2)
		# print(left)
		# print(right)

		ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

		right[l1] = r1
		left[r1] = l1

	print(ans)

main()
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
for i in range(0, n-2):
    for j in range(i+1,n-1):
        if s[i] == s[j]: continue
        for k in range(j+1,n):
            if s[i] == s[k] or s[j] == s[k] or j-i == k-j: continue
            ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

count = 0
#count second conditions satisfied
for i in range(n):
    for j in range(i+1,n):
        #search j - i = k - j ⇔ k = 2 * j - i
        k = 2 * j - i
        if k >= n: break
        if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]: count += 1
print((r * g * b) - count)