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

from itertools import product
n = int(input())

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

f = factorization(n)
l = []
for k, v in f:
    l += [k]*v
ans = n-1
for bit in product([True, False], repeat=len(l)):
    down = 1
    right = 1
    for i in range(len(l)):
        if bit[i]:
            down *= l[i]
        else:
            right *= l[i]
    ans = min(ans, down -1 + right - 1)
print(ans)






### FIXED CODE ###

from itertools import product
n = int(input())

ans = n-1
for a in range(1, int(n**0.5)+1):
    if n%a==0:
        b = n//a
        ans = min(ans, b+a-2)
print(ans)
### BUGGY CODE ###

while True:
  print('Hello')

### FIXED CODE ###

N = int(input())
ans = 0
for x in range(1,10):
    if N >= x:
        ans = ans + 1
for g in range(100,1000):
    if N >= g:
        ans = ans + 1
for m in range(10000,100000):
    if N >= m:
        ans = ans + 1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

l=[list() for i in range(n)]
s=[0]*n

def dfs(t,p):
  for c in l[t]:
    if c==p:
      continue
    s[c]+=s[t]
    dfs(c,t)

for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

for i in range(q):
  p,q=map(int,input().split())
  s[p-1]+=q

dfs(0,n)

print(*s)
print()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline

n,q=map(int,input().split())
t=[[] for _ in range(n)]
c=[0 for _ in range(n)]

for i in range(n-1):
  a,b=map(int,input().split())
  t[a-1].append(b-1)
  t[b-1].append(a-1)

for i in range(q):
  p,x=map(int,input().split())
  c[p-1]+=x

def dsf(ci,pi):
  for i in t[ci]:
    if i != pi:
      c[i] += c[ci]
      dsf(i, ci)

dsf(0,-1)

print(*c)
### BUGGY CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph,shortest_path,single_target_shortest_path,astar_path
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())

# G.add_nodes_from(list(range(1,N+1)))
for _ in range(M):
    A,B = map(int,input().split())
    G.add_edge(A, B)

# shortestPath = shortest_path(G,target=1)
# shortestPath = single_target_shortest_path(G,target=1)
ans = ["Yes"]
for i in range(2,N+1):
    try:
        shortestPath = astar_path(G,source=i,target=1)
        ans.append(shortestPath[1])
    except:
        print("No")
        exit()

print(*ans,sep="\n")
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
preds = bfs_predecessors(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i])
### BUGGY CODE ###

n = int(input())
List = list(map(int, input().split()))
count = 0

L2 = []

for i in range(n):
  L2.append(List[i])
  if List[i] <= min(L2):
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
List = list(map(int, input().split()))
count = 1
min = List[0]

for i in range(n):
  if min > List[i]:
    min =List[i]
    count += 1
print(count)
### BUGGY CODE ###

from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    if m == 0:
        return 1
    if m == 1 or n == 1 or n == 0:
        return n
    v = modpow(n, m // 2)
    v = v * v % MOD
    if m % 2 == 1:
        v = v * n % MOD
    return v


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    n, m, k = map(int, input().split())
    print(solve(n, m, k))

    # for n in range(3, 7):
    #     for m in range(1, 5):
    #         for k in range(0, n):
    #             assert solve_baka(n, m, k) == solve(n, m, k)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    ret = 1
    while m > 0:
        if m & 1:
            ret = ret * n % MOD
        n = n * n % MOD
        m >>= 1
    return ret


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    # for n in range(3, 7):
    #     for m in range(1, 5):
    #         for k in range(0, n):
    #             assert solve_baka(n, m, k) == solve(n, m, k)
    n, m, k = map(int, input().split())
    print(solve(n, m, k))


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

import re
N, Q = map(int, input().split())
S = input()
S_lr = []
for i in range(Q):
    l, r = map(int, input().split())
    s = S[l-1:r]
    print(len(re.findall('AC', s)))



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == 'AC' else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

def main():
    n = int(input())
    s = [None] + list(input())
    q = int(input())
    for _ in range(q):
        i, a, b = input().split()
        if i == "1":
            s[int(a)] = b
        else:
            print(len(set(s[int(a):int(b)+1])))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    bits = [BIT(n) for _ in range(26)]
    for i, si in enumerate(s, 1):
        bits[si].add(i, 1)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            bits[s[i-1]].add(i, -1)
            bits[ord(c)-a].add(i, 1)
            s[i-1] = ord(c)-a
        else:
            c = int(c)
            cnt = 0
            for bit in bits:
                is_in = bit.sum_(c) - bit.sum_(i-1)
                if is_in:
                    cnt += 1
            print(cnt)
            
            
class BIT:
    __slots__ = ["length", "data"]
    def __init__(self, length):
        self.data = [0]*(length+1)
        self.length = length
    
    def add(self, i, x):
        while i < self.length+1:
            self.data[i] += x
            i += i&-i
    
    def sum_(self, i):
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i&-i
        return x


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

# For taking integer inputs.
import math


def inp():
    return(int(input()))


# For taking List inputs.
def inlist():
    return(list(map(int, input().split())))


# For taking string inputs. Actually it returns a List of Characters, instead of a string, which is easier to use in Python, because in Python, Strings are Immutable.
def instr():
    s = input()
    return(list(s[:len(s)]))


# For taking space seperated integer variable inputs.
def invr():
    return(map(int, input().split()))


def getCount(start):
    l = r = 0
    for i in range(start-1, -1, -1):
        if a[i] == "<":
            l += 1
        else:
            break
    for i in range(start, n):
        if a[i] == ">":
            r += 1
        else:
            break

    return max(l, r)


a = input()
n = len(a)
c = 0
total = 0
flip = a[0]
for i in range(n+1):
    temp = getCount(i)
    total += temp
print(total)


### FIXED CODE ###

# For taking integer inputs.
import math


def inp():
    return(int(input()))


# For taking List inputs.
def inlist():
    return(list(map(int, input().split())))


# For taking string inputs. Actually it returns a List of Characters, instead of a string, which is easier to use in Python, because in Python, Strings are Immutable.
def instr():
    s = input()
    return(list(s[:len(s)]))


# For taking space seperated integer variable inputs.
def invr():
    return(map(int, input().split()))


a = input()
n = len(a)
coutn1 = [0] * (n+1)
coutn2 = [0] * (n+1)

for i in range(n):
    if a[i] == "<":
        coutn1[i+1] = coutn1[i] + 1
for i in range(n-1, -1, -1):
    if a[i] == ">":
        coutn2[i] = coutn2[i+1] + 1

total = 0

for i in range(n+1):
    total += max(coutn1[i], coutn2[i])
print(total)
### BUGGY CODE ###


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

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b=-b
  if b<A[ind]:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-A[ind])//d
  if dd==0:
    if b==A[ind]:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(B[ind],ind)
  
print(ans)


### FIXED CODE ###

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

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
PP = tuple(map(int,input().split()))

mind = -1
mmax = -1

for i in range(N-K+1):
    ksum = sum(PP[i:i+(K)])
    if ksum > mmax:
        mind = i
        mmax = ksum
        
        
maxrange = PP[mind:(mind+K)]

esum = 0
for m in maxrange:
    esum += (m+1)/2
    
print(esum)


### FIXED CODE ###

N,K = map(int,input().split())
PP = list(map(int,input().split()))


mind = -1
mmax = -1

sums = []
csum = 0

for i in range(N):
    p = PP[i]
    csum += (p+1)/2
    sums.append(csum)
    if i < K:
        if mmax < csum:
            mind = i
            mmax = csum
    else:
        ksum = csum - sums[(i-K)]
        if mmax < ksum:
            mind = i
            mmax = ksum


print(mmax)
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [0] * N
dp[1] = abs(H[1]-H[0])

for i in range(2, N):
    dp[i] = min([dp[i-k] + abs(H[i-k]-H[i]) for k in range(1, 1+K) if 0 <= i-k])

print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

dp = [0] * N
dp[1] = abs(H[1]-H[0])

for i in range(2, N):
    dp[i] = min([dp[i-k] + abs(H[i-k]-H[i]) for k in range(1, 1+K) if 0 <= i-k])

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

s=input()
n=len(s)
MOD=2019
l=[1]*n
for i in range(n-1,-1,-1):
  l[i]=int(s[i:n])%MOD
from collections import Counter
c=Counter(l)
ans=0
for i in c:
  ans+=c[i]*(c[i]-1)//2
  if i==0:
    ans+=c[i]
print(ans)


### FIXED CODE ###

s=input()
n=len(s)
l=[0]*2019
l[0]=1
k=0
mod=2019
r=1
for i in range(n-1,-1,-1):
  k+=int(s[i])*r
  k%=mod
  r*=10
  r%=mod
  l[k]+=1
ans=0
for i in l:
  ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

n, k, q = map(int, input().split(' '))
t = [int(input()) for i in range(q)] 

ans = [k for i in range(n)]

for i in range(max(t)):
    score = i + 1
    ans[i] += t.count(score)
    
res_list = [i - q for i in ans]


for i in res_list:
    if i > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections

n, k, q = map(int, input().split(' '))
t = [int(input()) for i in range(q)] 
 
ans = [k - q] * n

t_cnt = collections.Counter(t)
for i, j in t_cnt.items():
  ans[i-1] += j

for i in ans:
  if i > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

# coding:utf-8

import math


INF = float('inf')


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


N, X = inpl()
A = inpl()
E = [2 * (i + 1) + 1 for i in range(N)]
E[0] = 5
# print(E)
ans = INF
for k in range(1, N + 1):
    tmp = 0
    for i in range(1, N + 1):
        tmp += E[math.ceil(i / k) - 1] * A[N - i]

    ans = min(ans, tmp + (N + k) * X)
    # print(ans)

print(ans)

### FIXED CODE ###

# coding:utf-8


INF = float('inf')


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


N, X = inpl()
A = inpl()
B = [0]
for a in A:
    B.append(B[-1] + a)

ans = INF
for k in range(1, N + 1):
    e = 5
    cur = N - k
    tmp = e * (B[N] - B[cur]) + (N + k) * X
    cur -= k
    while True:
        tmp += e * (B[cur + k] - B[max(cur, 0)])
        if cur <= 0:
            break
        e += 2
        cur -= k

    ans = min(ans, tmp)

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

H,W,D=list(map(int,input().split()))
X=[(0,0) for i in range(H*W+1)]

for i in range(1,H+1):
	A=list(map(int,input().split()))
	for idx,a in enumerate(A):
		X[a]=(i,idx+1)

Q=int(input())
memo=[[0 for i in range(H*W+1)] for j in range(H*W+1)]
for i in range(Q):
	mp=0
	L,R=list(map(int,input().split()))
	now=L
	if memo[L][R]!=0:
		print(memo[L][R])
	else:
		while now!=R:
			mp+=abs(X[now+D][0]-X[now][0])+abs(X[now+D][1]-X[now][1])
			memo[L][R]=mp
			now+=D
		print(mp)
	

### FIXED CODE ###

H,W,D=list(map(int,input().split()))
X=[(0,0) for i in range(H*W+1)]

for i in range(1,H+1):
	A=list(map(int,input().split()))
	for idx,a in enumerate(A):
		X[a]=(i,idx+1)

Q=int(input())
L=[]
R=[]
S=[0]*(H*W+1)

for i in range(Q):
	l,r=list(map(int,input().split()))
	L.append(l)
	R.append(r)

for i in range(D+1,H*W+1):
	S[i]=S[i-D]+abs(X[i][0]-X[i-D][0])+abs(X[i][1]-X[i-D][1])

for i in range(Q):
	print(S[R[i]]-S[L[i]])
### BUGGY CODE ###

takahashi, aoki, K = list(map(int, input().split(" ")))

for _ in range(K):
    if takahashi >= 1:
        takahashi -= 1
    elif takahashi == 0 and aoki == 0:
        continue
    elif takahashi < 1 and aoki >= 1:
        aoki -= 1

print(takahashi, aoki)

### FIXED CODE ###

A, B, K = list(map(int, input().split(" ")))
times = min(A, K)
K -= times
print(A-times, max(B-K, 0))
### BUGGY CODE ###

import sys
from io import StringIO
import unittest

from collections import Counter

def resolve():
    n = int(input())
    l = [Counter(list(input())) for _ in range(n)]
    cnt = 0

    for i in range(len(l)):
        for j in range(i + 1, len(l)):
            if l[i] == l[j]:
                cnt += 1

    print(cnt)

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
acornistnt
peanutbomb
constraint"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
oneplustwo
ninemodsix"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa"""
        output = """4"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

import sys
from io import StringIO
import unittest

from collections import Counter

def resolve():
    n = int(input())
    l = [input() for _ in range(n)]
    cnt = 0
    ee = dict()

    for ll in l:
        tmp = ''.join(sorted(ll))

        if tmp in ee.keys():
            cnt += ee[tmp]
            ee[tmp] += 1
        else:
            ee[tmp] = 1

    print(cnt)

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3
acornistnt
peanutbomb
constraint"""
        output = """1"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """2
oneplustwo
ninemodsix"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa"""
        output = """4"""
        self.assertIO(input, output)


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

N = int(input())

res = 0
for i in range(1, N +1):
    if i < N:
        res += i

print(res)

### FIXED CODE ###

N = int(input())

print((N-1)*N //2 )
### BUGGY CODE ###

a,b = map(int, input().split())
l = list(map(int, input().split()))
max = 0
e = 0
temp = 0
pr = []

for i in range(a-b+1):
  temp = sum(l[i:i+b])
  if temp >= max:
    max = temp
    pr = l[i:i+b]

for j in pr:
  e += (j+1) / 2 
  
print(e)


### FIXED CODE ###

a,b = map(int, input().split())
l = [(int(i)+1)/2 for i in input().split()]

temp = sum(l[:b])
max = temp
for i in range(b,a):
  temp = temp + l[i] - l[i-b]
  if max < temp:
    max = temp
    
print(max)
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    x += (x & (-x))
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    x -= (x & (-x))
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a > x else -1))
  m = min(B)-1
  B = [x-m for x in B]
  BIT = [0]*(N+1)
  cnt = 0
  prev = 1
  for b in B[1:N+1]:
    BIT_update(BIT,prev,1)
    cnt += BIT_sum(BIT,b) # 右端がRとなる(L,R)対
    prev = b
    
  return cnt <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
    
answer = AA[right]
print(answer)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a>x else -1))
  m = min(B)-1
  B = [x-m for x in B]

  BIT = [0]*(N+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
answer = AA[right]

print(answer)