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

import itertools
n, m = map(int, input().split())
x, y, z, s = [0]*n, [0]*n, [0]*n, [0]*n
for i in range(n):
  x[i], y[i], z[i] = map(int, input().split())
output = 0
for i in list(itertools.combinations(range(n), m)):
  sum_x = 0
  sum_y = 0
  sum_z = 0
  for j in range(m):
    sum_x += x[i[j]]
    sum_y += y[i[j]]
    sum_z += z[i[j]]
  if output <= abs(sum_x)+abs(sum_y)+abs(sum_z):
    output = abs(sum_x)+abs(sum_y)+abs(sum_z)
print(output)

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  N, M = map(int, input().split())
  ppp = []
  ppm = []
  pmp = []
  pmm = []
  mpp = []
  mpm = []
  mmp = []
  mmm = []
  for _ in range(N):
    x, y, z = map(int, input().split())
    ppp.append(x+y+z)
    ppm.append(x+y-z)
    pmp.append(x-y+z)
    pmm.append(x-y-z)
    mpp.append(-x+y+z)
    mpm.append(-x+y-z)
    mmp.append(-x-y+z)
    mmm.append(-x-y-z)
  ppp = sorted(ppp, key=lambda x:-x)
  ppm = sorted(ppm, key=lambda x:-x)
  pmp = sorted(pmp, key=lambda x:-x)
  pmm = sorted(pmm, key=lambda x:-x)
  mpp = sorted(mpp, key=lambda x:-x)
  mpm = sorted(mpm, key=lambda x:-x)
  mmp = sorted(mmp, key=lambda x:-x)
  mmm = sorted(mmm, key=lambda x:-x)

  ans = max(sum(ppp[:M]), sum(ppm[:M]), sum(pmp[:M]), sum(pmm[:M]),
            sum(mpp[:M]), sum(mpm[:M]), sum(mmp[:M]), sum(mmm[:M]))
  print(ans)


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

A,B,N=map(int,input().split())
ans=0
t=min(B+1,N+1)
t_min=min(0,t-100)
for x in range(t_min,t):
    a=int(A*x/B)
    b=A * int(x/B)
    ans=max(ans,a-b)

print(ans)

### FIXED CODE ###

A,B,N=map(int,input().split())
ans=0
t=min(B+1,N+1)

for x in range(t-2,t):
    a=int(A*x/B)
    b=A * int(x/B)
    ans=max(ans,a-b)

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

from sys import stdin
#n = int(stdin.readline().rstrip())
n,k = map(int, stdin.readline().rstrip().split())
#S = [list(map(int, stdin.readline().rstrip().split())) for _ in range(h)]#hの定義を忘れずに
p = list(map(int, stdin.readline().rstrip().split()))

ans = 0

for i in range(n-k+1):
    sums = 0
    for j in range(k):
        num = p[i+j]
        sum = 0
        for u in range(num):
            sum += u+1
        sum = sum/num
        sums += sum
    ans = max(ans, sums)

print(ans)


### FIXED CODE ###

from sys import stdin
#n = int(stdin.readline().rstrip())
#l = list(map(int, stdin.readline().rstrip().split()))
N,K = map(int, stdin.readline().rstrip().split())
P = list(map(int, stdin.readline().rstrip().split()))

Q = [(p+1)/2 for p in P]
c = [0]
for q in Q:
    c.append(c[-1] + q)

ans = 0
for i in range(K,N+1):
    ans = max(ans, c[i] - c[i-K])
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import collections
import numpy as np
from scipy.sparse.csgraph import shortest_path

N, X, Y = list(map(int, input().split()))

d_table = []
for i in range(N):  # 2 * 10 ** 3
    d_list = [0] * N
    if i != 0:
        d_list[i - 1] = 1
    if i != N - 1:
        d_list[i + 1] = 1
    d_table.append(d_list)

d_table[X - 1][Y - 1] = 1
d_table[Y - 1][X - 1] = 1
adj = np.array(d_table)
d_matrix = shortest_path(adj, method="FW")

counter = collections.Counter(list(d_matrix.flatten()))
ans_s = []
for k in range(1, N):  # 2 * 10 ** 3
    c = counter[float(k)]
    c = c // 2
    ans_s.append(str(c))
ans = "\n".join(ans_s)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import collections
from collections import defaultdict

N, X, Y = list(map(int, input().split()))

skip_d = abs(X - Y)
d_count = defaultdict(lambda: 0)
# d_table = []
for i in range(N):
    # d_list = []
    for j in range(N):
        if i == j:
            d = 0
            d_count[d] += 1
            # d_list.append(d)
            continue
        # Normal
        min_index = min(i, j)
        max_index = max(i, j)

        if min_index <= X - 1 and Y - 1 <= max_index:
            # 両方外にいる
            d = abs(i - j) - skip_d + 1
        elif X - 1 <= min_index and max_index <= Y - 1:
            # 両方中にいる
            d_1 = abs(i - j)
            x2min = abs(min_index - (X - 1))
            max2y = abs((Y - 1) - max_index)
            d_2 = x2min + max2y + 1
            d = min(d_1, d_2)
        elif max_index <= Y - 1:
            # elif min_index <= X - 1 and X - 1 <= max_index < Y - 1:
            # 大きい方が中にいる
            d_1 = abs(i - j)
            max2y = abs((Y - 1) - max_index)
            min2y = abs(min_index - (Y - 1)) - skip_d + 1
            d_2 = max2y + min2y
            d = min(d_1, d_2)
        elif X - 1 <= min_index:
            # elif X - 1 <= min_index < Y - 1 and Y - 1 <= max_index:
            # 小さい方が中にいる
            d_1 = abs(i - j)
            d_2 = (abs(max_index - (X - 1)) - skip_d + 1) + abs((X - 1) - min_index)
            d = min(d_1, d_2)

        # d_list.append(d)
        d_count[d] += 1
    # d_table.append(d_list)

ans_s = []
for k in range(1, N):  # 2 * 10 ** 3
    c = d_count[k]
    c = c // 2
    ans_s.append(str(c))
ans = "\n".join(ans_s)
print(ans)
### BUGGY CODE ###

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

m = n + 1
s = 0

for i in range(1,m):
    if s < n:
        c = a.count(i)
        s = s + c
        print(c)
    elif s >= n:
        print('0')


### FIXED CODE ###

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

s = [0]*(n)

for i in range(n-1):
    s[a[i]-1] = s[a[i]-1] + 1
    
for j in range(n):
    print(s[j])
### BUGGY CODE ###

MOD = 10**9 + 7
n = int(input())
ans = set()

def dfs(a:int, b:int, digit:int, memo:set):
    u = a^b
    v = a+b
    
    if u > n or v > n:
        return 0
    
    else:        
        if digit == 0:
            memo.add((u,v))
            return 0
            
        else:
            dfs(a+pow(2,digit-1), b+pow(2,digit-1), digit-1, memo)
            dfs(a+pow(2,digit-1), b, digit-1, memo)
            dfs(a, b, digit-1, memo)
            
dfs(0,0,60,ans)

print(len(ans) % MOD)


### FIXED CODE ###

import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())


MOD = 10**9+7

n = ni()
n_bit = len(bin(n)[2:])

dp = [[0]*4 for _ in range(n_bit+1)]
dp[0][0] = 1

for bit in range(n_bit):
    digit = int(bin(n)[2+bit:2+bit+1])
    
    if digit:
        dp[bit+1][0] = (dp[bit][0]) % MOD
        dp[bit+1][1] = (dp[bit][0] + dp[bit][1]) % MOD
        dp[bit+1][2] = (dp[bit][1]) % MOD
        dp[bit+1][3] = (dp[bit][1] + 3*dp[bit][2] + 3*dp[bit][3]) % MOD
        
    else:
        dp[bit+1][0] = (dp[bit][0] + dp[bit][1]) % MOD
        dp[bit+1][1] = (dp[bit][1]) % MOD
        dp[bit+1][2] = (dp[bit][1] + dp[bit][2]) % MOD
        dp[bit+1][3] = (2*dp[bit][2] + 3*dp[bit][3]) % MOD
        
print(sum(dp[n_bit]) % MOD)
### BUGGY CODE ###

from math import factorial

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod = 10**9+7

if K==1:print(0)
else:
  def comb(n,k):
    return factorial(n)*pow(factorial(n-k)*factorial(k), -1, mod)

  A1=sorted(A)
  A2=A1[::-1]
  
  ans=0
  for i in range(N-K+1):
    ans += (A2[i]-A1[i])*comb(N-i-1,K-1)
  ans %= mod

  print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod = 10**9+7

if K==1:print(0)
else:
  factorial=[1 for i in range(N+1)]
  for i in range(1,N+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i % mod
  
  def comb(n,k):
    return factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod)

  A1=sorted(A)
  A2=A1[::-1]
  
  ans=0
  for i in range(N-K+1):
    ans += (A2[i]-A1[i])*comb(N-i-1,K-1)
  ans %= mod

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf")]*N
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	for j in range(1, min(K + 1, N - i)):
		dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])
### BUGGY CODE ###

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

if n%k == 0:
    print(0)
else:
    while True:
        tmp = abs(n-k)

        if n > tmp:
            n = tmp
        else:
            break
    print(n)


### FIXED CODE ###

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

a = n%k
while True:
    tmp = abs(a-k)

    if a > tmp:
        a = tmp
    else:
        break
print(a)
### BUGGY CODE ###

import numpy as np

N, K = map(int, input().split())
hs = np.array(list(map(int, input().split())))

i = 0
total_cost = 0
 
a = np.zeros(N, int)
a[0] = 0
a[1] = abs(hs[1] - hs[0])

for i in range(2, N):
    bmin = float('inf')
    for j in range(max(i-K,0),i):
        bmin = min(bmin, a[j] + abs(hs[i] - hs[j]))    
    a[i] = bmin
print(a[-1])


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
hs = np.array(list(map(int, input().split())))

i = 0
total_cost = 0
 
a = np.zeros(N, dtype=np.int64)
a[0] = 0
a[1] = abs(hs[1] - hs[0])

for i in range(2, N):
    k = min(K,i)
    a[i] = np.min(a[i-k:i] + np.abs(hs[i] - hs[i-k:i]))    
print(a[-1])
### BUGGY CODE ###

def func(n):
    cnt = 0
    a = int(n**0.5)
    for x in range(1, a+1):
        if(x**2+3+2*x > n):
            break
        for y in range(x, a+1):
            if(x**2+y**2+x*y+x+y+1 > n):
                break
            for z in range(y, a+1):
                if(x**2+y**2+z**2+x*y+y*z+z*x == n):
                    if(x == y == z):
                        cnt += 1
                    elif(x != y and y != z and z != x):
                        cnt += 6
                    else:
                        cnt += 3
                    break
                elif(x**2+y**2+z**2+x*y+y*z+z*x > n):
                    break
        
    return cnt

N = int(input())
    
for i in range(1, N+1):
    print(func(i))

### FIXED CODE ###

def func(n):
    cnt = 0
    a = int(n**0.5)
    for x in range(1, a+1):
        for y in range(x, a+1):
            z = y
            while(x**2+y**2+z**2+x*y+y*z+z*x <= n):
                if(x**2+y**2+z**2+x*y+y*z+z*x == n):
                    if(x == y == z):
                        cnt += 1
                    elif(x != y and y != z and z != x):
                        cnt += 6
                    else:
                        cnt += 3    
                    break
                z += 1
    return cnt

N = int(input())
    
for i in range(1, N+1):
    print(func(i))
### BUGGY CODE ###

n, m = map(int, input().split())
id = [x for x in range(1, n + 1)]
for i in range(m):
    l, r = map(int, input().split())
    id = [x for x in id if l <= x <= r]
print(len(id))

### FIXED CODE ###

n, m = map(int, input().split())
id = set(i for i in range(1, n + 1))
L = []
R = []
for i in range(m):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
print( min(R) - max(L) + 1 if min(R) - max(L) + 1 > 0 else 0)
### BUGGY CODE ###

n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for i in range(m):
    for j in range(n_bit):
        dp[j | can_open[i]] = min(dp[j | can_open[i]], dp[j]+cost[i])

print(dp[-1] if dp[-1] != INF else -1)

### FIXED CODE ###

n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [[INF]*n_bit for _ in range(m+1)]
dp[0][0] = 0

# 配る
for i in range(m):
    for j in range(n_bit):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

        if (j | can_open[i]) <= n_bit:
            dp[i+1][j | can_open[i]
                    ] = min(dp[i+1][j | can_open[i]], dp[i+1][j]+cost[i])

print(dp[-1][-1] if dp[-1][-1] != INF else -1)
### BUGGY CODE ###

import numpy as np
from collections import deque
H,W = map(int, input().split())
CH,CW = map(int, input().split())
DH,DW = map(int, input().split())
[CH,CW,DH,DW] = [CH-1,CW-1,DH-1,DW-1]
S = np.array([list(input()) for i in range(H)])
M = 10 ** 9
Distance = np.ones((H,W))*M
Distance[CH,CW] = 0
[nowH,nowW] = [CH,CW]
q0 = deque([])
q0.append([nowH,nowW])
q1 = deque([])
while len(q0) != 0 or len(q1) != 0:
  if len(q0) != 0:
    [nowH,nowW] = q0.popleft()
  else:
    [nowH,nowW] = q1.popleft()
  if [nowH,nowW] == [DH,DW]:
    break
  for i in range(-2,3):
    for j in range(-2,3):
      if nowH+i >= 0 and nowW+j >= 0 and nowH+i < H and nowW+j < W:
        if (abs(i) + abs(j)) == 1:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q0.append([nowH+i,nowW+j])
            elif [nowH+i,nowW+j] in q1:
              q0.append([nowH+i,nowW+j])
              q1.remove([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW],Distance[nowH+i,nowW+j])
        elif (abs(i) + abs(j)) >= 2:
          if S[nowH+i,nowW+j] == '.':
            if Distance[nowH+i,nowW+j] == M:
              q1.append([nowH+i,nowW+j])
            Distance[nowH+i,nowW+j] = min(Distance[nowH,nowW]+1,Distance[nowH+i,nowW+j])       
if Distance[DH,DW] == M:
  print(-1)
else:
  print(int(Distance[DH,DW]))  

### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
CH,CW = map(lambda x: int(x) - 1, input().split())
DH,DW = map(lambda x: int(x) - 1, input().split())
S = [input() for i in range(H)]
INF = 10 ** 9
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]
h = CH
w = CW
Distance = [[INF] * W for _ in range(H)]
Distance[h][w] = 0
q = deque(())
q.append((h,w))
while q:
  h,w = q.popleft()
  if [h,w] == [DH,DW]:
    break
  for i,j in walk:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w]
      q.appendleft((hwalk,wwalk))
  for i,j in warp:
    hwalk = h + i
    wwalk = w + j
    if 0 <= hwalk < H and 0 <= wwalk < W and S[hwalk][wwalk] == '.' and Distance[h][w] + 1 < Distance[hwalk][wwalk]:
      Distance[hwalk][wwalk] = Distance[h][w] + 1
      q.append((hwalk,wwalk))
print(int(Distance[DH][DW]) if Distance[DH][DW] != INF else -1)
### BUGGY CODE ###

n = int(input())
slist = []
ans = 0

sdic = {}
for i in range(n):
    s = str(sorted(list(input())))
    if s in sdic.keys():
        ans += sdic[s]
        sdic[s] += 1
    else:
        sdic[s] = 1

print(ans)

### FIXED CODE ###

import collections
n = int(input())
s_list = ["".join(sorted(input())) for _ in range(n)]
s_dict = {}
ans = 0
for s in s_list:
    if s in s_dict:
       ans += s_dict[s]
       s_dict[s] += 1
    else:
        s_dict[s] = 1
print(ans)
### BUGGY CODE ###

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


def triangle(num):
    a,b,c=num
    if a<(b+c) and b<(a+c) and c<(a+b):
        return True
    else:
        return False
ans=0
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            num=[l[i],l[j],l[k]]
            ans+=triangle(num)
print(ans)


### FIXED CODE ###

from bisect import bisect_left
n=int(input())
l=list(map(int,input().split()))
l.sort()

ans=0
for a in range(n-2):
    for b in range(a+1,n-1):
        ans+=max(0,bisect_left(l, l[a] + l[b])-b-1)
        
        
print(ans)
### BUGGY CODE ###

import copy
N = list(input())
nums = len(N)
mass = [1 for _ in range(nums)]

prev = N[0]
dicr = {}
dicl = {}
for i in range(1, len(N)):
  if prev == "R" and N[i] == "L":
    dicr[i-1] = True
    dicl[i] = True
  prev = N[i]
for i in range(len(N)):
  if i not in dicr and i not in dicl:
    mass[i] = 0
    if N[i] == "R":
      for k, v in sorted(dicr.items()):
        if i < k:
          rest = k-i
          if rest%2 == 0:
            mass[k] += 1
          else:
            mass[k+1] += 1
          break
    else:
      for k, v in sorted(dicl.items(), reverse=True):
        if i > k:
          rest = i-k
          if rest%2 == 0:
            mass[k] += 1
          else:
            mass[k-1] += 1
          break
mass = [str(m) for m in mass]
print(' '.join(mass))

### FIXED CODE ###

import bisect
N = list(input())
nums = len(N)
mass = [1 for _ in range(nums)]

prev = N[0]
dicr = []
dicl = []
all = []
for i in range(1, len(N)):
  if prev == "R" and N[i] == "L":
    dicr.append(i-1)
    dicl.append(i)
    all.append(i)
    all.append(i-1)
  prev = N[i]
all = set(all)
dicr = sorted(dicr)
dicl = sorted(dicl)
for i in range(len(N)):
  if i not in all:
    mass[i] = 0
    if N[i] == "R":
      ind = dicr[bisect.bisect_left(dicr, i)]
      rest = ind-i
      if rest%2 == 0:
        mass[ind] += 1
      else:
        mass[ind+1] += 1
    else:
      ind = dicl[bisect.bisect_left(dicl, i)-1]
      rest = ind-i
      if rest%2 == 0:
        mass[ind] += 1
      else:
        mass[ind-1] += 1
mass = [str(m) for m in mass]
print(' '.join(mass))
### BUGGY CODE ###

# 素数リスト生成
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**8)

# 素因数分解
def factorint(x):
  d = {}
  for k in PS:
    if(x % k== 0):
      m = 1
      while(x % (k**m) == 0):
        m += 1
      d[k] = m - 1
      x = x / (k ** (m - 1))
      if x == 1:
        break
  return d

n, m = map(int, input().split())
f = factorint(m)
idx = [i for i in f.values()]

def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret

ans = 1
for i in range(len(idx)):
  ans *= com(idx[i] + n - 1, n - 1) % (10 ** 9 + 7)

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

### FIXED CODE ###

# 素数リスト生成
def sieve(x):
    if x < 2: return []
    primes = [i for i in range(x)]
    primes[1] = 0
    for p in primes:
        if p > x ** (1/2): break
        if p == 0: continue
        for np in range(2 * p, x, p): primes[np] = 0
    return [p for p in primes if p != 0]

PS = sieve(10**6)

# 素因数分解
def factorint(x):
  d = {}
  for k in PS:
    if(x % k== 0):
      m = 1
      while(x % (k**m) == 0):
        m += 1
      d[k] = m - 1
      x = x / (k ** (m - 1))
      if x == 1:
        break
  return d

n, m = map(int, input().split())
f = factorint(m)
idx = [i for i in f.values()]
# 10^6より大きい素因数があったときの処理
re = 1
for k, v in f.items():
  re *= k**v
if m // re != 1:
  idx.append(1)


def fact(n):
  ret = 1
  for i in range(1, n + 1):
    ret *= i
  return ret
def com(n, r):
  if n - r < r: r = n - r
  ret = 1
  for i in range(n-r+1, n+1):
    ret *= i
  for j in range(1, r+1):
    ret //= j
  return ret

ans = 1
for i in range(len(idx)):
  ans *= com(idx[i] + n - 1, n - 1) % (10 ** 9 + 7)

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

def cordineatecompression(list):
    n=len(list)
    test=[(list[i],i) for i in range(0,n)]
    ans=[-1 for i in range(0,n)]
    test.sort()
    co=1
    val=test[0][0]
    ans[test[0][1]]=co
    for i in range(1,n):
        if val==test[i][0]:
            ans[test[i][1]]=co
        else:
            val=test[i][0]
            co+=1
            ans[test[i][1]]=co
    return ans

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

def median(num):
    data=[0]*N
    for i in range(N):
        if A[i]>num:
            data[i]=1
        else:
            data[i]=-1
    for i in range(1,N):
        data[i]+=data[i-1]
    data=[0]+data
    data=cordineatecompression(data)

    ans=0

    BIT=[0]*(N+2)
    n=N+1
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(0,N+1):
        val=data[i]
        ans+=BIT_query(val)
        BIT_update(val,1)
    test=N*(N+1)//2-ans
    return test>=((N*(N+1)//2)//2+1)

start=0
end=10**9
while end-start>1:
    test=(end+start)//2
    if median(test):
        end=test
    else:
        start=test

if median(start):
    print(start)
else:
    print(end)


### FIXED CODE ###

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

def median(num):
    row=[0]*N
    for i in range(N):
        if A[i]>num:
            row[i]=1
        else:
            row[i]=-1
    m=0
    data=[0]
    for i in range(0,N):
        data.append(data[-1]+row[i])
        m=min(m,data[i+1])
    data=[data[i]-m+1 for i in range(N+1)]
    ans=0
    BIT=[0]*(N+2)
    n=N+1
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    for i in range(0,N+1):
        val=data[i]
        ans+=BIT_query(val)
        BIT_update(val,1)
    test=N*(N+1)//2-ans
    return test>=((N*(N+1)//2)//2+1)

start=0
end=10**9
while end-start>1:
    test=(end+start)//2
    if median(test):
        end=test
    else:
        start=test

if median(start):
    print(start)
else:
    print(end)
### BUGGY CODE ###

# -*- coding: utf-8 -*-# -*- coding: utf-8 -*-
"""
Created on Sat Jan 19 12:14:33 2019
DP_F
@author: maezawa
"""
import itertools as itr

s = input()
t = input()

ls = len(s)
lt = len(t)

dp = [['']*(lt+1) for _ in range(ls+1)]

for i, j in itr.product(range(1, ls+1), range(1, lt+1)):
    if s[i-1] == t[j-1]:
        dp[i][j] = dp[i-1][j-1]+s[i-1]
    else:
        if len(dp[i-1][j]) > len(dp[i][j-1]):
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i][j-1]
    #print((i,j), dp[i][j])

print(dp[-1][-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 17 09:02:00 2019
DPF3
@author: maezawa
"""

s = input()
t = input()

ns = len(s)
nt = len(t)

dp = [[0 for _ in range(nt+1)] for _ in range(ns+1)]

for si in range(ns):
    for ti in range(nt):
        if s[si] == t[ti]:
            dp[si+1][ti+1] = max(dp[si][ti]+1, dp[si+1][ti], dp[si][ti+1])
        else:
            dp[si+1][ti+1] = max(dp[si+1][ti], dp[si][ti+1])

ans = ''
si = ns
ti = nt
while si > 0 and ti > 0:
    if dp[si][ti] == dp[si-1][ti]: 
        si -= 1
    elif dp[si][ti] == dp[si][ti-1]:
        ti -= 1
    else:
        ans = s[si-1] + ans
        si -= 1
        ti -= 1

print(ans)