CodeEff/ECCO huggingface dataset:
# Original solution
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n = ini()
s = list(ins())
t = sorted(s)
ans = 0
for i in range(n):
    if t[i] != "R":
        break 
    if s[i] != t[i]:
        ans += 1
print(ans)


# Optimized solution
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n = ini()
s = list(ins())
n = s.count("R")
t = sorted(s)
ans = 0
for i in range(n):
    if s[i] != t[i]:
        ans += 1
print(ans)
# Original solution
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n = ini()
s = list(ins())
n = s.count("R")
t = sorted(s)
ans = 0
for i in range(n):
    if s[i] != t[i]:
        ans += 1
print(ans)


# Optimized solution
import sys
input = sys.stdin.readline
ins = lambda: input().rstrip()
ini = lambda: int(input().rstrip())
inm = lambda: map(int, input().split())
inl = lambda: list(map(int, input().split()))
out = lambda x: print('\n'.join(map(str, x)))

n = ini()
s = list(ins())
n = s.count("R")
ans = 0
for i in range(n):
    if s[i] != "R":
        ans += 1
print(ans)
# Original solution
n,s,*w=open(0)
r=[-1]
n=int(n)
a=i=0
while i<n:
  if'W'>s[i]:r+=i,
  else:w+=i,
  i+=1
for w in w:
  if r.pop()>w:a+=1
  else:break
print(a)

# Optimized solution
_,s=open(0)
print((s[:s.count('R')].count('W')))
# Original solution
import sys
readline = sys.stdin.readline
from collections import deque

def solve():
    N = int(readline())
    C = readline().rstrip()

    R, W = 'R', 'W'
    reds = deque(i for i in range(len(C)) if C[i] == 'R')
    whites = deque(i for i in range(len(C)) if C[i] == 'W')

    count = 0
    while len(whites) > 0 and len(reds) > 0 and whites[0] < reds[-1]:
        reds.pop()
        whites.popleft()
        count += 1
    
    print(count)

solve()

# Optimized solution
import sys
readline = sys.stdin.readline

def solve():
    N = int(readline())
    C = readline().rstrip()

    reds = [i for i in range(len(C)) if C[i] == 'R']
    whites = [i for i in range(len(C)) if C[i] == 'W']

    i = 0
    n = min(len(reds), len(whites))
    while i < n and reds[-1-i] > whites[i]:
        i += 1
    
    print(i)

solve()
# Original solution
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    C = list(input().strip())
    last = N
    ans = 0
    for i in range(N):
        if C[i] == 'W':
            for j in reversed(range(i+1, last)):
                if C[j] == 'R':
                    ans += 1
                    last = j
                    break
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)


# Optimized solution
import sys
sys.setrecursionlimit(10**6)


def main(input, print):
    N = int(input())
    C = list(input().strip())
    last = N
    ans = 0
    for i in range(N):
        if C[i] == 'W':
            has_r = False
            for j in reversed(range(i+1, last)):
                if C[j] == 'R':
                    ans += 1
                    last = j
                    has_r = True
                    break
            if not has_r:
                break
    print(ans)


if __name__ == '__main__':
    main(sys.stdin.readline, print)
# Original solution
from itertools import accumulate
from math import ceil
N = int(eval(input()))
A = list(map(int, input().split()))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = 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.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


# BIT準備
BIT = BinaryIndexedTree(N)
# 答えをにぶたん
lo, hi = -1, max(A) + 1  # sample2などに対応するためにhiを設定
while hi - lo > 1:
    m = (hi + lo) // 2

    # m以上かどうかで分類
    binary = [(1 if a >= m else -1) for a in A]
    binary = list(accumulate(binary))

    # BITの初期化
    BIT.reset()

    # 和が0以上となる連続部分列を数える
    tmp = 0

    # 転倒数っぽくやる
    binary_sorted = {b: i for i, b in enumerate(sorted(binary), start=1)}
    ans = 0
    for j, b in enumerate(binary):
        tmp += BIT.sum(binary_sorted[b]) + (binary_sorted[b] >= 0)
        BIT.add(binary_sorted[b], 1)

    # 連続する部分列の個数の半分以上和が0以上となる区間が存在するかで場合分け
    if tmp >= ceil(((N * (N + 1)) / 2) / 2):
        lo = m
    else:
        hi = m

print(lo)


# Optimized solution
from itertools import accumulate
from math import ceil
N = int(eval(input()))
A = list(map(int, input().split()))


class BinaryIndexedTree:
    def __init__(self, n):
        self.size = 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.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


# BIT準備
BIT = BinaryIndexedTree(N)
# 答えをにぶたん
lo, hi = -1, max(A) + 1  # sample2などに対応するためにhiを設定
while hi - lo > 1:
    m = (hi + lo) // 2

    # m以上かどうかで分類
    binary = [(1 if a >= m else -1) for a in A]
    binary = list(accumulate(binary))

    # BITの初期化
    BIT.reset()

    # 和が0以上となる連続部分列を数える
    tmp = 0

    # 転倒数っぽくやる
    binary_sorted = {b: i for i, b in enumerate(sorted(binary), start=1)}
    ans = 0
    for j, b in enumerate(binary):
        tmp += BIT.sum(binary_sorted[b]) + (b >= 0)
        BIT.add(binary_sorted[b], 1)

    # 連続する部分列の個数の半分以上和が0以上となる区間が存在するかで場合分け
    if tmp >= ceil(((N * (N + 1)) / 2) / 2):
        lo = m
    else:
        hi = m

print(lo)
# Original solution
import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N = I()
A = LI()


def f(x):  # A[l:r+1] の中央値が x 以上になる (l,r) の個数が、全体の半分以上あるか
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N for b in B]
    # Bi <= Bj たる (i,j) の個数を数える
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b+1)
        bit.update(b+1,1)
    return True if count >= (N*(N+1)+3)//4 else False


ok = 1
ng = 10**9+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)


# Optimized solution
import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N = I()
A = LI()


def f(x):  # A[l:r+1] の中央値が x 以上になる (l,r) の個数が、全体の半分以上あるか
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N+1 for b in B]  # 全て正になるように補正
    # Bi <= Bj たる (i,j) の個数を数える
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b)
        bit.update(b,1)
    if count >= (N*(N+1)+3)//4:
        return True
    return False


ok = 1
ng = 10**9+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)
# Original solution
import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N = I()
A = LI()


def f(x):  # A[l:r+1] の中央値が x 以上になる (l,r) の個数が、全体の半分以上あるか
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N+1 for b in B]  # 全て正になるように補正
    # Bi <= Bj たる (i,j) の個数を数える
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b)
        bit.update(b,1)
    if count >= (N*(N+1)+3)//4:
        return True
    return False


ok = 1
ng = 10**9+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print(ok)


# Optimized solution
# 座標圧縮した場合

import sys
from itertools import accumulate
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class BIT:
    def __init__(self,init_value):
        self.n = len(init_value)
        self.tree = [0]*(self.n+1)
        for i in range(1,self.n+1):
            x = init_value[i-1]
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)

    def update(self,i,x):  # i(1-index)番目の値を+x
        while i <= self.n:
            self.tree[i] += x
            i += i & (-i)
        return

    def query(self,i):  # 1番目からi(1-index)番目までの和を返す
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & (-i)
        return res


N = I()
A = LI()
C = sorted(list(set(A)))
dict_A = {}  # dict_A[a] = (a は A の中で何番目に小さい値か)
dict_C = {}  # dict_C[i] = (A の中で i 番目に小さい値)
for i in range(1,len(C)+1):
    dict_C[i] = C[i-1]
    dict_A[C[i-1]] = i
A = [dict_A[a] for a in A]


def f(x):  # A[l:r+1] の中央値が x 以上になる (l,r) の個数が、全体の半分以上あるか
    B = [0] + [1 if A[i] >= x else -1 for i in range(N)]
    B = list(accumulate(B))
    B = [b+N+1 for b in B]  # 全て正になるように補正
    # Bi <= Bj たる (i,j) の個数を数える
    bit = BIT([0]*(2*N+2))
    count = 0
    for i in range(N+1):
        b = B[i]
        count += bit.query(b)
        bit.update(b,1)
    if count >= (N*(N+1)+3)//4:
        return True
    return False


ok = 1
ng = 10**5+1
while ok+1 < ng:
    mid = (ok+ng)//2
    if f(mid):
        ok = mid
    else:
        ng = mid

print((dict_C[ok]))
# Original solution
from itertools import accumulate
from math import ceil
 
N = int(eval(input()))
A = list(map(int, input().split()))
 
if N == 1:
    print((A[0]))
    exit()
 
 
class BinaryIndexedTree:
    def __init__(self, n):
        self.size = 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.size:
            self.bit[i] += x
            i += (i & -i)
 
    def reset(self):
        self.bit = [0] * (self.size + 1)
 
 
BIT = BinaryIndexedTree(N)  # Binaryの先頭の分
lo, hi = -1, 10 ** 9 + 1
while hi - lo > 1:
    # Xは中央値候補
    X = (hi + lo) // 2
 
    # X以上なら1、X未満なら-1に変換
    Binary = [(1 if a >= X else -1) for a in A]
 
    # 累積和をとる
    Binary = list(accumulate(Binary))
 
    # BITを初期化
    BIT.reset()
 
    # 転倒数っぽいものを数える
    inversion = 0
    Binary_sorted = {b: i for i, b in enumerate(sorted(Binary), start=1)}
    for j, b in enumerate(Binary):
        inversion += BIT.sum(Binary_sorted[b]) + (b >= 0)
        BIT.add(Binary_sorted[b], 1)
 
    if inversion >= ceil((N * (N + 1) / 2) / 2):
        lo = X
    else:
        hi = X
 
print(lo)

# Optimized solution
import math

n = int(input())
lst = list(map(int, input().split()))
 
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
            
def judge(x, lst, n):
 
    length = len(lst)
    all_pair = (length*(length-1) // 2) + length
    
    lst_r = [-1 if i < x else 1 for i in lst]
    lst_accum = []
    a = 0
    for i in lst_r:
        a += i
        lst_accum.append(a)
    
    bit = Bit(n)
    lst_accum_sorted = {b: i for i, b in enumerate(sorted(lst_accum), start=1)}
    count = 0
    for j, b in enumerate(lst_accum):
        count += bit.sum(lst_accum_sorted[b]) + (b >= 0)
        bit.add(lst_accum_sorted[b], 1)
        
    if count >= math.ceil(all_pair/2):
        return True
    else:
        return False
 
    
sorted_lst = sorted(lst)
low = 0
high = len(lst) - 1
while high - low >1:
    t = (low+high) // 2
    i = sorted_lst[t]
    if judge(i, lst, n):
        low = t
    else:
        high = t
        
print(sorted_lst[high]) if judge(sorted_lst[high], lst, n) else print(sorted_lst[low])
# Original solution
from itertools import accumulate
def add(B,a,n):#リストに値を追加する関数
    x = a
    while x <= n:
        B[x] += 1
        x += x&(-x)

def sums(B,a):#a番目までの和
    x = a
    S = 0
    while x != 0:
        S += B[x]
        x -= x&(-x)
    return S


def invnumber(n, S):# #{(i,j)| i<j and S[i]<=S[j]}
    B = [0]*(n*2 + 1)
    invs = 0
    for i in range(n):
        s = S[i] + n
        invs += sums(B, s)
        add(B, s, n*2)
    return invs

N = int( eval(input()))
A = list( map( int, input().split()))
R = max(A)+1
L = 0
c = (N*(N-1)//2 + 1)//2

while R - L > 1:
    M = (R+L)//2
    S = [0]*N
    if A[0] >= M:
        S[0] = 1
    else:
        S[0] = -1
    for i in range(1,N):
        if A[i] >= M:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(N,S) >= c:
        L = M
    else:
        R = M
print(L)


# Optimized solution
def add(B,a,n):#リストに値を追加する関数
    x = a
    while x <= n:
        B[x] += 1
        x += x&(-x)

def sums(B,a):#a番目までの和
    x = a
    S = 0
    while x != 0:
        S += B[x]
        x -= x&(-x)
    return S


def invnumber(n, S):# #{(i,j)| i<j and S[i]<=S[j]}
    B = [0]*(n*2 + 1)
    invs = 0
    for i in range(n):
        s = S[i] + n
        invs += sums(B, s)
        add(B, s, n*2)
    return invs

N = int( eval(input()))
A = list( map( int, input().split()))
R = max(A)+1
L = 0
c = (N*(N+1)//2 + 1)//2
while R - L > 1:
    M = (R+L)//2
    S = [0]*(N+1)
    for i in range(1,N+1):
        if A[i-1] >= M:
            S[i] = S[i-1] + 1
        else:
            S[i] = S[i-1] - 1
    if invnumber(N+1,S) >= c:
        L = M
    else:
        R = M
print(L)
# Original solution

from bisect import bisect_left
from math import ceil
# >= 3.3
# from collections.abc import Sequence
# < 3.3
from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def __len__(self):
        return self.size

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

    def add(self, i, v):
        while i <= self.size:
            self.tree[i] += v
            i += i & -i


N = int(eval(input()))
a = [0] + [int(s) for s in input().split()]


def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(s)

    def f(v):
        i = bisect_left(ss, v)
        return i + 1

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        fi = f(s[i])
        count += b.sum(fi)
        b.add(fi, 1)

    return count


# i: 0, 1, ..., 10 ** 9 + 10
# x: 10 ** 9 + 10, ..., 0
counts = LazySequence(lambda i: count_lr(10 ** 9 + 10 - i), 10 ** 9 + 10)
ans = 10 ** 9 + 10 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)


# Optimized solution

from bisect import bisect_left
from math import ceil
import sys
if sys.version_info[0:2] >= (3, 3):
    from collections.abc import Sequence
else:
    from collections import Sequence


class LazySequence(Sequence):
    def __init__(self, f, n):
        self.f = f
        self.n = n

    def __len__(self):
        return self.n

    def __getitem__(self, i):
        if not (0 <= i < self.n):
            raise IndexError
        return self.f(i)


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def __len__(self):
        return self.size

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

    def add(self, i, v):
        while i <= self.size:
            self.tree[i] += v
            i += i & -i


N = int(eval(input()))
a = [0] + [int(s) for s in input().split()]
# a = [0] * (N + 1)


def count_lr(x):
    s = [0] * (N + 1)
    for i in range(1, N + 1):
        s[i] = s[i - 1] + (1 if a[i] >= x else -1)

    ss = sorted(set(s))
    ind = {v: i + 1 for i, v in enumerate(ss)}

    b = Bit(N + 10)
    count = 0
    for i in range(N + 1):
        j = ind[s[i]]
        count += b.sum(j)
        b.add(j, 1)

    return count


# i: 0, 1, ..., 10 ** 9
# x: 10 ** 9, ..., 0
counts = LazySequence(lambda i: count_lr(10 ** 9 - i), 10 ** 9 + 1)
ans = 10 ** 9 - bisect_left(counts, ceil(N * (N + 1) / 4))
print(ans)
# Original solution
class BIT:
    """1-indexed BIT
    """

    def __init__(self, size: int):
        """サイズを指定して BIT を初期化します。
        """
        self.__size = size
        self.__bit = [0] * (self.__size+1)

    def add(self, idx: int, val: int):
        """位置 idx (1-indexed) に値 val をたす。
        :param idx: 値を追加したいインデックス
        :param val: 追加したい値
        """
        while idx <= self.__size:
            self.__bit[idx] += val
            idx += idx & (-idx)

    def sum(self, idx: int)->int:
        s = 0
        while idx > 0:
            s += self.__bit[idx]
            idx -= idx & (-idx)
        return s


def median_of_medians(N: int, A: list) -> int:
    def check(x: int)->int:
        bit = BIT(2 * N + 1)
        s = 0
        a = 0
        for i in range(N):
            s += bit.sum(a + N)
            bit.add(a + N, 1)
            a = a + (1 if x <= A[i] else - 1)

        s += bit.sum(a + N)

        return s

    alpha = sorted(A)
    l, r = 0, N
    while r - l > 1:
        m = (r + l + 1) // 2
        if 2*check(alpha[m]) >= (N * (N + 1)) // 2:
            l = m
        else:
            r = m

    return alpha[l]


if __name__ == "__main__":
    N = int(eval(input()))
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)


# Optimized solution

def median_of_medians(N: int, A: list)->int:
    def search(c):
        bar = N
        r = 0
        res_nega = 0
        dp_arr = [0]*(2*N+1)
        for i in range(N):
            dp_arr[bar] += 1
            if A[i] < c:
                r += dp_arr[bar]
                bar += 1
            else:
                r -= (dp_arr[bar-1])
                bar -= 1
            res_nega += r
        return res_nega

    # binary search
    a_sorted = sorted(A)
    left = 0
    right = N
    mid = N // 2
    C = N*(N+1) // 2
    while True:
        if search(a_sorted[mid]) <= C // 2:
            if mid == N-1:
                break
            elif search(a_sorted[mid+1]) > C // 2:
                break
            else:
                left = mid
                mid = (mid + right) // 2
        else:
            right = mid + 1
            mid = (mid + left) // 2

    return a_sorted[mid]


if __name__ == "__main__":
    N = int(eval(input()))
    A = [int(s) for s in input().split()]
    ans = median_of_medians(N, A)
    print(ans)
# Original solution
n = int(eval(input()))
A = list(map(int, input().split()))

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    S = [0] * n
    S[0] = -1 + 2 * int(A[0] >= mid)
    for i in range(n-1):
        S[i+1] = S[i] - 1 + 2 * int(A[i] >= mid)
    bit = Bit(n+2)
    ans = 0

    Smin = min(S)
    S = [S[i]-min(S)+1 for i in range(n)]
    #print(S)
    for i, p in enumerate(S):
        bit.add(p, 1)
        ans += bit.sum(p) - 1  # 「S[i] >= S[i]」をカウントしないように1を引く

    #print(le, ri, mid, ans)

    if ans >= (n*(n-1))//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)
    


# Optimized solution
n = int(eval(input()))
A = list(map(int, input().split()))

# n = 4
# A = [i+1 for i in range(n)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#print((n*(n+1))//(2*2))

le = -1
ri = max(A) + 1
mid = (le + ri) // 2
while ri - le > 1:
    S = [0] * n
    S[0] = -1 + 2 * int(A[0] >= mid)
    for i in range(n-1):
        S[i+1] = S[i] - 1 + 2 * int(A[i+1] >= mid)
    bit = Bit(n+2)
    ans = 0
    for i in range(n):
        if S[i] >= 0:
            ans += 1

    #print("S OK")

    Smin = min(S)
    S = [S[i] - Smin + 1 for i in range(n)]

    #print("S OK2")
    #print(S)
    for i, p in enumerate(S):
        
        bit.add(p, 1)

        ans += bit.sum(p) - 1  # 「S[i] >= S[i]」をカウントしないように1を引く
        #print(i,ans)


    #print(le, ri, mid, ans)

    if ans >= (n*(n+1))//(2*2):
        le = mid
    else:
        ri = mid
    mid = (le + ri) // 2

print(le)