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

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = list(Counter(a).items())

for i in range(n):
    r = 0
    for x, y in c:
        if x == a[i]:
            r += max(((y-1)*(y-2)//2), 0)
        else:
            r += (y-1)*y //2
    print(r)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
x = []
r = 0
for x, y in c.items():
    r += (y-1)*y//2

for i in range(n):
    print(r-(c[a[i]]-1))
### BUGGY CODE ###

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


def check(m, bin):
    global a
    s = 0
    for b in a:
        if bin & 1:
            s += b
            if s > m:
                return False
        bin >>= 1
    return s == m


for m in ms:
    for i in range(1, 2 ** n - 1):
        if check(m, i):
            print('yes')
            break
    else:
        print('no')

### FIXED CODE ###

from itertools import combinations

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

l = set(sum(t) for i in range(n) for t in combinations(a, i + 1))

for m in map(int, input().split()):
    print('yes' if m in l else 'no')
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

for i in range(Q):
    l, r = map(int, input().split())
    bubun = S[l - 1:r]
    print(bubun.count("AC"))

### 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 ###

N = int(input())
A = list(map(int, input().split()))
cnt = 0
for i in A:
    a, b, c = A.count(i), A.count(i+1), A.count(i+2)
    sums = a+b+c
    if sums > cnt:
        cnt = sums
print(cnt)

### FIXED CODE ###

from collections import Counter 
N = int(input())
A = Counter(list(map(int, input().split())))
cnt = 0
for i in A:
    sums = A[i] + A[i+1] + A[i+2]
    if sums > cnt:
        cnt = sums
print(cnt)
### BUGGY CODE ###

n=int(input())
a=list(input().split())
ans=1
f=0
for i in a:
    ans=ans*int(i)
    if f==0 and ans>1000000000000000000:
        f=1
    if int(i)==0:
        f=0
        print(0)
        exit()
if f==1:
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

n=int(input())
a=list(input().split())
ans=1
f=0
i=0
while(i<n):
    if f==0:
        ans=ans*int(a[i])
    if f==0 and ans>1000000000000000000:
        f=1
    if int(a[i])==0:
        print(0)
        exit()
    i+=1
if f==1:
    print(-1)
    exit()
print(ans)
### BUGGY CODE ###

import itertools


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

C = list(itertools.permutations(V, N))

n = len(C)
ans = 0
for c in C:
    for v in range(n):
        a = C[v][0]
        for i in range(1, N):
            a = (a + C[v][i]) / 2
        ans = max(ans, a)
print(ans)

### FIXED CODE ###

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

C = sorted(V)

ans = 0
a = C[0]
for i in range(1, N):
    a = (a + C[i]) / 2
ans = max(ans, a)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
from itertools import combinations

mod = 10 ** 9 + 7


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

    c = combinations(ls, 2)

    ans = 0

    for cc in c:
        ans += cc[0] * cc[1] % mod

    print(ans % mod)


main()



### FIXED CODE ###

#!/usr/bin/env python3
MOD = 10 ** 9 + 7


class ModInt:
    def __init__(self, x):
        if type(x) is str:
            x = int(x)
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x)
            if isinstance(other, ModInt)
            else ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x)
            if isinstance(other, ModInt)
            else ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x)
            if isinstance(other, ModInt)
            else ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(self.x * pow(other.x, MOD - 2, MOD))
            if isinstance(other, ModInt)
            else ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD))
            if isinstance(other, ModInt)
            else ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x)
            if isinstance(other, ModInt)
            else ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(other.x * pow(self.x, MOD - 2, MOD))
            if isinstance(other, ModInt)
            else ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD))
            if isinstance(other, ModInt)
            else ModInt(pow(other, self.x, MOD))
        )


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

    ans = ModInt(0)

    sm = sum(ls)

    for i in range(n):
        ans += ls[i] * sm

    sub = ModInt(0)
    for i in range(n):
        sub += ls[i] * ls[i]

    ans -= sub

    ans = ans / 2

    print(ans)


main()
### BUGGY CODE ###

from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

Q, K = inpl()
now = {K}
dist = [0 for _ in range(N+1)]
visited = [False for _ in range(N+1)]
visited[K] = visited[0] = True
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            if visited[nb]:
                continue
            dist[nb] = dist[na] + nc
            visited[nb] = True
            now.add(nb)
    if all(visited):
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])

### FIXED CODE ###

from collections import defaultdict
def inpl(): return [int(i) for i in input().split()]

path = defaultdict(lambda: [])
N = int(input())
for _ in range(N-1):
    a, b, c = inpl()
    path[a].append((b,c))
    path[b].append((a,c))

ctr = 1
Q, K = inpl()
now = [K]
dist = [0 for _ in range(N+1)]
while True:
    for na in now.copy():
        na = now.pop()
        for nb, nc in path[na]:
            dist[nb] = dist[na] + nc
            path[nb].remove((na,nc))
            now.append(nb)
            ctr += 1
    if ctr >=  N:
        break
for i in range(Q):
    x, y = inpl()
    print(dist[x]+dist[y])
### BUGGY CODE ###

R,G,B,n = map(int, input().split())
ans = 0
for r in range(n//R+1):
    for g in range(n//G+1):
        ball = R*r + G*g
        if ball > n or (n-ball)%B!=0: continue
        ans += 1
print(ans)

### FIXED CODE ###

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

a = max(R, G, B)
if a == R:
  b = max(G, B)
elif a == G:
  b = max(B, R)
else:
  b = max(R, G)
c = min(R, G, B)
for i in range(N//a+1):
  for j in range((N-a*i)//b+1):
    if ((N-a*i)-b*j)%c == 0:
      ans += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = 0
for i in range(N):
	for j in range(N):
		if A[i] < B[j]:
			for k in range(N):
				if B[j] < C[k]:
					ans += 1
print(ans)


### FIXED CODE ###

from bisect import bisect_right, bisect_left

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

ans = 0

for bi in range(N):
    ai_max = bisect_left(A, B[bi])
    ci_min = bisect_right(C, B[bi])
    ans += (ai_max) * (N - ci_min)

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

Q = int(input())

import heapq

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -heapq.nsmallest(1,L)[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

for _ in range(Q):
  row = [int(x) for x in input().split()]
  if row[0] == 1:
    f1(row[1],row[2])
  else:
    f2()


### FIXED CODE ###

Q = int(input())

import heapq
import sys
input = sys.stdin.readline

INF = 10**18
L = []
R = []
heapq.heappush(L,INF)
heapq.heappush(R,INF)
L_size = 0
R_size = 0
sum_b = 0
sum_L = 0
sum_R = 0

def f1(a,b):
  global sum_b,L_size,R_size,sum_L,sum_R
  sum_b += b
  L_max = -heapq.heappop(L)
  R_min = heapq.heappop(R)
  sum_L -= L_max
  sum_R -= R_min
  X = sorted([L_max,a,R_min])
  if L_size == R_size:
    heapq.heappush(L,-X[0])
    heapq.heappush(L,-X[1])
    heapq.heappush(R,X[2])
    L_size += 1
    sum_L += X[0] + X[1]
    sum_R += X[2]
  else:
    heapq.heappush(L,-X[0])
    heapq.heappush(R,X[1])
    heapq.heappush(R,X[2])
    R_size += 1
    sum_L += X[0]
    sum_R += X[1] + X[2]
  return

def f2():
  min_value = sum_b
  min_x = -L[0]
  if L_size == R_size:
    min_value += sum_R - sum_L
  else:
    min_value += sum_R - sum_L + min_x
  print(min_x,min_value)

QUERY = [[int(x) for x in input().split()] for _ in range(Q)]
for q in QUERY:
  if q[0]&1:
    f1(q[1],q[2])
  else:
    f2()
### BUGGY CODE ###

n,k,c=map(int,input().split())
s=input()
l=len(s)
cand=[]
for i in range(l):
    if s[i]=='o':
        cand.append(i+1)
        cnt1=[0]*(n+c+2)
        cnt2=[0]*(n+c+2)

for i in range(l):
    if s[i]=='o':
        cnt1[i+1]=max(cnt1[i],cnt1[i-c]+1)
    else:
        cnt1[i+1]=cnt1[i]
for i in range(l-1,-1,-1):
    if s[i]=='o':
        cnt2[i+1]=max(cnt2[i+2],cnt2[i+c+2]+1)
    else:
        cnt2[i+1]=cnt2[i+2]
ans=[]
for i in range(len(cand)):##嘘に見える
    tmp=cand[i]
    if cnt1[tmp-1]+cnt2[tmp+1]<k:
        ans.append(tmp)
for val in ans:
    print(val)


### FIXED CODE ###

n,k,c=map(int,input().split())
s=input()
l=len(s)
cand=[]
for i in range(l):
    if s[i]=='o':
        cand.append(i+1)
cnt1=[0]*(n+c+2)
cnt2=[0]*(n+c+2)        

for i in range(l):
    if s[i]=='o':
        cnt1[i+1]=max(cnt1[i],cnt1[i-c]+1)
    else:
        cnt1[i+1]=cnt1[i]
for i in range(l-1,-1,-1):
    if s[i]=='o':
        cnt2[i+1]=max(cnt2[i+2],cnt2[i+c+2]+1)
    else:
        cnt2[i+1]=cnt2[i+2]
ans=[]
for i in range(len(cand)):##嘘に見える
    tmp=cand[i]
    if cnt1[tmp-1]+cnt2[tmp+1]<k:
        print(tmp)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N-1):
    temp=0
    for j in range(i+1,N):
        temp+=A[j]
    ans+=A[i]*(temp%(10**9+7))
print(ans%(10**9+7))


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
s=sum(A)
for i in range(N-1):
    s-=A[i]
    ans+=(A[i]*(s))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros((n+1,s+1),dtype = int)
    for i,ai in enumerate(a):
        if ai > s:
            continue
        for j in range(n):
            dp[n-j][ai:] += dp[n-j-1][:-ai]
        dp[1][ai] += 1
    ans = 0
    for i in range(n+1):
        dpi = dp[i]
        ans = (ans+(dpi[s]*two[n-i])%mod)%mod
    print(ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    two = [1]*(n+1)
    for i in range(n):
        two[i+1] = two[i]*2%mod
    dp = np.zeros(3010,dtype = int)
    dp[0] = 1
    for i,ai in enumerate(a):
        ndp = dp*2
        ndp[ai:] += dp[:-ai]
        ndp %= mod
        dp = ndp
    print(dp[s])
    return

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

N = int(input())

S = input()

min_num = N+1

for v in range(N):
    min_num = min(S[0:v].count('W')+S[v:N].count('E'),min_num)
print(min_num)

### FIXED CODE ###

N = int(input())

S = input()

min_num = N+1

W = []
E = []

w_cnt = 0
e_cnt = 0

for i in range(N):
    if S[i] == 'W':
        w_cnt += 1
    W.append(w_cnt)

for i in range(N-1,0,-1):
    min_num = min(min_num,W[i-1]+e_cnt)
    if S[i] == 'E':
        e_cnt += 1

print(min(min_num,e_cnt))
### BUGGY CODE ###

import itertools

N = int(input())
A = list(map(int,(input().split())))
Asum = 0
c_list = list(itertools.combinations(A, 2))

for l in c_list:
    Asum = Asum + l[0]*l[1]

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

### FIXED CODE ###

N = int(input())
A = list(map(int,(input().split())))
total = 0
result = 0
MOD = pow(10,9)+7
l = []

for i in range(N):
    total += A[i]
    l.append(total)#累積和

for i,num in enumerate(l):
    temp = total-num #A[i+1]+A[i+2]+...+A[N]
    result += temp*A[i]#A[i](A[i+1]+A[i+2]+...+A[N])の総和

print(result%MOD)
### BUGGY CODE ###

import sys

def input(): return sys.stdin.readline().strip()

s = input()
q = int(input())

for i in range(q):
    query = input().split()
    if query[0] == "1":
        s = s[::-1]
    else:
        if query[1] == "1":
            s = query[2] + s
        else:
            s = s + query[2]
print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())

rev = False
for i in range(q):
    query = input().split()
    if query[0] == "1":
        rev ^= True
    else:
        if (query[1] == "1" and not rev) or (query[1] == "2" and rev):
            s.appendleft(query[2])
        else:
            s.append(query[2])

if rev:
    print("".join(list(s)[::-1]))
else:
    print("".join(list(s)))
### BUGGY CODE ###

n = int(input())
T = []
for _ in range(n-1):
    T += [list(map(int, input().split()))]
T.sort()
P = [0]+[-1]*(n-1)
T_sub = []
while T:
    for t in T:
        u, v, w = t
        pu, pv = P[u-1], P[v-1]
        if (pu < 0) & (pv < 0):
            T_sub += [t]
        elif (pu >= 0) & (pv < 0):
            P[v-1] = (pu+(w%2))%2
        elif (pv >= 0) & (pu < 0):
            P[u-1] = (pv+(w%2))%2
    T = T_sub
for p in P: print(p)

### FIXED CODE ###

n = int(input())
L = [[] for _ in range(n+1)]
R = [[] for _ in range(n+1)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    w %= 2
    L[u] += [[u, v, w]]
    R[v] += [[v, u, w]]
P = [[] for _ in range(2*n+2)]
P[1] += (L[1]+R[1])
L[1] = R[1] = []
for i in range(1, 2*n):
    for _, v, w in P[i]:
        P[i+2-w] += (L[v]+R[v])
        L[v] = R[v] = []
A = []
for p in P[1::2]: A += p
B = set([u for u, *_ in A])
for i in range(1, n+1): print(1 if i in B else 0)
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

R, C, K = MI()
item = {(0,0):0}

for i in range(K):
    r_, c_, v_, = MI()
    item[(r_ - 1,c_ - 1)] = v_

dp = [[[0 for _ in range(C + 2)] for _ in range(R + 2)] for _ in range(4)]

for i in range(R + 1):
    for j in range(C + 1):
        for k in range(4):
            a = dp[k][i][j]
            if (i,j) in item:
                v = item[(i,j)]
            else:
                v = 0

            if k == 3:
                dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                continue
            dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
            dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
            dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))



### FIXED CODE ###

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def main():
    R, C, K = NMI()
    item = [[0] * (C + 1) for i in range(R + 1)]

    for i in range(K):
        r_, c_, v_, = NMI()
        item[r_ - 1][c_ - 1] = v_

    dp = [[[0 for _ in range(C + 2)] for _ in range(R + 2)] for _ in range(4)]

    for i in range(R + 1):
        for j in range(C + 1):
            for k in range(4):
                a = dp[k][i][j]
                v = item[i][j]

                if k == 3:
                    dp[0][i + 1][j] = max(a, dp[0][i + 1][j])
                    continue
                dp[0][i + 1][j] = max(a, a + v, dp[0][i + 1][j])
                dp[k][i][j + 1] = max(a, dp[k][i][j + 1])
                dp[k + 1][i][j + 1] = max(a + v, dp[k + 1][i][j + 1])

    print(max(dp[0][R][C], dp[1][R][C], dp[2][R][C], dp[3][R][C]))

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

n = int(input())
a = [input() for i in range(n)]
for i in range(n):
    b = a[i]
    del a[i]
    print(max(a))
    a.insert(i ,b)


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a, reverse=True)
for i in range(n):
    if b[0] == b[1]:
        print(b[0])
    else:
        if a[i] == b[0]:
            print(b[1])
        else:
            print(b[0])
### BUGGY CODE ###

N, M = tuple([int(x) for x in input().split(' ')])
A = [int(x) for x in input().split(' ')]

for i in range(M):
    B, C = tuple([int(x) for x in input().split(' ')])
    A.extend([C]*B)

A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###

N, M = tuple([int(x) for x in input().split(' ')])
A = [int(x) for x in input().split(' ')]
minA = min(A)

BC = []
for i in range(M):
    BC.append(tuple([int(x) for x in input().split(' ')]))

BC.sort(key=lambda x:x[1], reverse=True)

sumB = 0
for B, C in BC:
    if C <= minA:
        break
    sumB += B
    A.extend([C]*B)
    if sumB >= N:
        break

A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n,k=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
p=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
ck = []

#最大のリストを選定
for i in range(0,n-k+1):
    ck.append(sum(p[i:i+k]))

#計算
print((max(ck)+k)/2.0)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n,k=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
p=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
#最大のリストを選定
before_pi = p[0]
before_sum = sum(p[0:k])+ 0.0
suml = [sum(p[0:k])]
for i in range(1,n-k+1):
    before_sum = before_sum - before_pi+p[i+k-1]
    suml.append(before_sum)
    before_pi = p[i]

#計算
print((max(suml)+k)/2.0)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(input().split(), dtype=np.int32)
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = (((A > x) * 2) - 1).cumsum()
  B -= B.min() - 1
  L = B.max() + 1
  BIT = [0]*L
  cnt = 0
  
  for b in [1] + list(B):
    x = b
    while x:
      cnt += BIT[x]
      x -= (x & (-x))
    x = b
    while x < L:
      BIT[x] += 1
      x += (x & (-x))
  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)
### BUGGY CODE ###

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L=[0]*(n1+1)
    R=[0]*(n2+1)
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    i=0
    j=0
    global cnt
    cnt += (right-left)
    for k in range(left,right):
#        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+2<right:
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)
    elif left+1<right:
        mid =left+1
        merge(A,left,mid,right)

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)



### FIXED CODE ###

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(float("inf"))
    R.append(float("inf"))
    """
    L=[0]*(n1+1)
    R=[0]*(n2+1)
    for i in range(n1):
        L[i]=A[left+i]
    for i in range(n2):
        R[i]=A[mid+i]
    L[n1]=float("inf")
    R[n2]=float("inf")
    """
    i=0
    j=0
    for k in range(left,right):
        global cnt
        cnt+=1
        if L[i]<=R[j]:
            A[k]=L[i]
            i=i+1
        else:
            A[k]=R[j]
            j=j+1

def mergeSort(A,left,right):
    if left+1<right:
        mid=(left+right)//2
        mergeSort(A,left,mid)
        mergeSort(A,mid,right)
        merge(A,left,mid,right)

n=int(input())
S=list(input().split())
for i in range(n):
    S[i]=int(S[i])
cnt=0
mergeSort(S,0,n)
for i in range(n):
    if i==n-1:
        print(S[i])
    else:
        print(S[i],end=" ")
print(cnt)
### BUGGY CODE ###

N = input()
nums = []
for i in range(N):
     nums.append(input())

profit = nums[1] - nums[0]
for a in range(N):
     for b in range(a):
          if (nums[a] - nums[b]) > profit:
               profit = nums[a] - nums[b]

print profit

### FIXED CODE ###

N = input()
nums = []
for i in range(N):
     nums.append(input())
profit = nums[1] - nums[0]
min = nums[0]
for a in range(1, N):
     if nums[a] - min > profit:
          profit = nums[a] - min

     if nums[a] < min:
               min = nums[a]
print profit