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

N, Q = (int(i) for i in input().split())
S = input()

res = []
for num in range(Q):
    l, r = (int(i) for i in input().split())
    S2 = S[l-1:r]
    flag = False
    cnt = 0
    for chr in S2:
        if chr == "A":
            flag = True
        elif chr == "C" and flag == True:
            cnt += 1
            flag = False
        else:
            flag = False
    res.append(cnt)

for i in res:
    print(i)



### FIXED CODE ###

N, Q = (int(i) for i in input().split())
S = input()

code = [0] * N
cnt = 0
index = 0
flag = False
for chr in S: 
    if chr == "A":
            flag = True
    elif chr == "C" and flag == True:
        cnt += 1
        flag = False
    else:
        flag = False
    code[index] = cnt
    index += 1

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

h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]

c=[[0]*w for i in range(h)]
for i in range(h):
  for j in range(w):
    c[i][j]=abs(a[i][j]-b[i][j])

dp=[[[0]*(80*(h+w)+1) for i in range(w)] for j in range(h)]
dp[0][0][c[0][0]]=1
for i in range(h):
  for j in range(w):
    for k in range(80*(i+j)+1):
      if dp[i-1][j][abs(k-c[i][j])]==1 or dp[i][j-1][abs(k-c[i][j])]==1 or dp[i-1][j][k+c[i][j]]==1 or dp[i][j-1][k+c[i][j]]:
        dp[i][j][k]=1

for i in range(80*(h+w)+1):
  if dp[h-1][w-1][i]==1:
    print(i)
    break

### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  h,w=map(int,input().split())
  a=[list(map(int,input().split())) for i in range(h)]
  b=[list(map(int,input().split())) for i in range(h)]
  dp=[[[0]*(80*(h+w+1)+1) for i in range(w)] for j in range(h)]
  dp[0][0][abs(a[0][0]-b[0][0])]=1
  for i in range(h):
    for j in range(w):
      c=abs(a[i][j]-b[i][j])
      if i!=0 or j!=0:
        for k in range(80*(i+j+1)+1):
          dp[i][j][k]=dp[i-1][j][abs(k-c)]|dp[i-1][j][k+c]|dp[i][j-1][abs(k-c)]|dp[i][j-1][k+c]
  for i in range(80*(h+w+1)+1):
    if dp[h-1][w-1][i]==1:
      print(i)
      break

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

N = int(input())
ans = []

for i in range(N):
    Si = input()
    if Si in ans:
        continue
    else:
        ans.append(Si)

print(len(ans))

### FIXED CODE ###

N = int(input())
ans = set()
for i in range(N):
    Si = input()
    ans.add(Si)
print(len(ans))
### BUGGY CODE ###

import math

N=int(input())
d=list(map(int, input().strip().split()))
ans=0

ave_d=sum(d)/N

diff=[]

for num1 in d:
    diff.append(num1-ave_d)

diff2=[]

for num2 in diff:
    diff2.append(num2**2)

dis_d=sum(diff2)/N

std_d=math.sqrt(dis_d)

for i in range(int(ave_d-std_d),int(ave_d+std_d+1)):
    ABC=0
    ARC=0
    for j in range(int(N)):

        if d[j]<i:
            ABC+=1
        else:
            ARC+=1

    if ARC==ABC:
        ans+=1

print(ans)


### FIXED CODE ###

N=int(input())
d=list(map(int, input().strip().split()))
ans=0

d.sort()

#for i in range(int(d[int(N/2)-1]),int(d[int(N/2)]+1)):

print(int(d[int(N/2)])-int(d[int(N/2)-1]))
### BUGGY CODE ###

n,k=map(int, input().split())
an=[int(i) for i in input().split()]
from scipy.misc import comb

an=sorted(an)
r_an=list(reversed(an))

max1=0
min1=0
for i in range(1,n-k+2):
    max1+=an[-i]*comb(n-i,k-1,exact=True)
    min1+=r_an[-i]*comb(n-i,k-1,exact=True)
print((max1-min1)%(10**9+7))

### FIXED CODE ###

n,k=map(int, input().split())
an=[int(i) for i in input().split()]

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r=min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 5
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2,N+1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

an=sorted(an)
r_an=list(reversed(an))

max1=0
min1=0
for i in range(1,n-k+2):
    c=cmb(n-i,k-1,p)
    max1=max1 + an[-i]*c%p
    min1=min1 + r_an[-i]*c%p
print((max1-min1)%p)
### BUGGY CODE ###

n, m = map(int, input().split())
ab = []
for _ in range(n):
  a, b = map(int, input().split())
  ab.extend([a for _ in range(b)])
  
ab.sort()
print(sum(ab[:m]))

### FIXED CODE ###

n,m,*t = map(int, open(0).read().split())
ans = 0
for a, b in sorted(zip(t[::2], t[1::2])):
  ans += min(b, m)*a
  m -= b
  if m <= 0:
    print(ans)
    break
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

vvv_odd = vvv[::2]
vvv_even = vvv[1::2]

odd_vocab = set(vvv_odd)
even_vocab = set(vvv_even)


def calc_rewrite_number(vvv_each, vocab):
    max_count = -1
    for v in vocab:
        max_count = max(max_count, vvv_each.count(v))
    len_vvv_each = len(vvv_each)
    return len_vvv_each - max_count


# Calculation for odd and even elements in vvv
n_rewrite = 0
n_rewrite += calc_rewrite_number(vvv_odd, odd_vocab)
n_rewrite += calc_rewrite_number(vvv_even, even_vocab)
if len(odd_vocab & even_vocab) == 1:
    n_rewrite += len(vvv_odd)

# Output
print(n_rewrite)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

if len(set(vvv)) == 1:
    print(N // 2)
    exit()

vvv_odd = vvv[::2]
vvv_even = vvv[1::2]

dp_odd = [0] * max(vvv_odd)
dp_even = [0] * max(vvv_even)

for v_odd, v_even in zip(vvv_odd, vvv_even):
    dp_odd[v_odd - 1] += 1
    dp_even[v_even - 1] += 1

max_appear_odd = max(dp_odd)
max_appear_even = max(dp_even)

max_odd_val = dp_odd.index(max_appear_odd) + 1
max_even_val = dp_even.index(max_appear_even) + 1

if max_odd_val == max_even_val:
    next_appear_odd = sorted(dp_odd, reverse=True)[1]
    next_appear_even = sorted(dp_even, reverse=True)[1]
    if next_appear_odd > next_appear_even:
        max_appear_odd = next_appear_odd
    else:
        max_appear_even = next_appear_even

n_replace = N // 2 - max_appear_odd
n_replace += N // 2 - max_appear_even

print(n_replace)
### BUGGY CODE ###

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in px:
    value[p] += x

from collections import deque
todo = deque([(1,0)])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append((y,x))

print(*value[1:])

### FIXED CODE ###

N,Q = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]
px = [list(map(int,input().split())) for i in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in px:
    value[p] += x

from collections import deque
todo = deque([(1,0)])
while len(todo) > 0:
    x,parent = todo.pop()
    value[x] += value[parent]
    for y in graph[x]:
        if y == parent:
            continue
        todo.append((y,x))

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    As = [int(input()) for _ in range(m)]

    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in As:
        dp[1] = 1
    else:
        dp[1] = 0

    for i in range(2, n+1):
        if i in As:
            continue
        dp[i] = dp[i-1] + dp[i-2]
        dp[i] %= 1000000007

    print(dp[-1])


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    As = set([int(input()) for _ in range(m)])
    mod = 1000000007

    dp = [0] * (n + 1)
    dp[0] = 1
    if 1 not in As:
        dp[1] = 1

    for i in range(2, n+1):
        if i in As:
            continue
        dp[i] = dp[i-1] + dp[i-2]

    ans = dp[n] % mod
    print(ans)


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

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

facts = [1]
invs = [1]
for i in range(1, n+k):
    f = i*facts[i-1]%MOD
    facts.append(f)
    invs.append(pow(f, MOD-2, MOD))

def nCk(n, k):
    return (facts[n]*invs[k]*invs[n-k])%MOD
def nHk(n, k):
    return nCk(n+k-1, n-1)

ans = []
for i in range(2, k+2):
    p = i//2
    ans_i = 0
    for q in range(min(p+1, n+1)):
        if k-i+q < 0:
            continue
        if i%2 > 0: # odd
            ans_iq = pow(2, q, MOD)*nCk(p, q)*nHk(k-(i-1)+q, n-q)%MOD
        else: # even
            ans_iq = 0
            if q > 0 and k-i+q > 0:
                ans_iq = (ans_iq+pow(2, q-1, MOD)*nCk(p-1, q-1)*nHk(k-(i-1)+(q-1), n-q))%MOD
            if q < p:
                ans_iq = (ans_iq+pow(2, q, MOD)*nCk(p-1, q)*nHk(k-(i-1)+q, n-q))%MOD
            # print(ans_iq)
        ans_i = (ans_i + ans_iq)%MOD
    ans.append(ans_i)

for a in ans+ans[-2::-1]:
    print(a)


### FIXED CODE ###

# Acknowledge: https://atcoder.jp/contests/arc102/submissions/3127544
MOD = 998244353
k, n = map(int, input().split())

facts = [1]
invs = [1]
for i in range(1, n+k):
    f = (i*facts[i-1])%MOD
    facts.append(f)
    invs.append(pow(f, MOD-2, MOD))

def nCk(n, k):
    return (facts[n]*invs[k]*invs[n-k])%MOD

memo = []
for p in range(1, (k+3)//2):
    i = 2*p+1
    tmp = 0
    for t in range(min(p+1, n+1)):
        if k-i+t < 0:
            continue
        res = nCk(p, t)
        res *= nCk(n+k-i, k-i+t)
        res *= pow(2, t, MOD)
        tmp = (tmp+res)%MOD
    memo.append(tmp)

ans = []
for i in range(1, k):
    ans.append(memo[(i-1)//2])
for a in ans+[memo[-1]]+ans[::-1]:
    print(a)
### BUGGY CODE ###

""" this is C - Triangular Relationship"""

n, m = [int(i) for i in input().split()]

count = 0

for i in range(1, n+1):
    for j in range(i, n+1):
        for k in range(j, n+1):
            a = i+j
            b = j+k
            c = k+i
            if a%m == 0 and b%m == 0 and c%m == 0:
                if i == j and j == k:
                    count += 1
                elif i != j and j == k:
                    count += 3
                elif i == j and j != k:
                    count += 3
                else:
                    count += 6

print(count)


### FIXED CODE ###

""" AtCoder """

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

if K % 2 == 0:
    print((N//K) ** 3 + (((N - (K//2))//K + 1) ** 3))
else:
    print((N//K) ** 3)
### BUGGY CODE ###

from fractions import Fraction
N = int(input())
A = []
for _ in range(N):
    A.append(Fraction(input()))
ans=0
for i in range(N):
    for j in range(i+1,N):
        if (A[i]*A[j]).denominator==1:
            ans += 1
print(ans)


### FIXED CODE ###

N = int(input())
a = [[0 for j in range(19)] for i in range(19)]
ans=0
for _ in range(N):
    A=input()
    if A.find('.') > 0:
        count2 = 10 - len(A) + A.find('.')
        count5 = 10 - len(A) + A.find('.')
    else:
        count2 = 9
        count5 = 9
    tmp = int(A.replace('.', ''))
    while count2 < 18:
        if tmp % 2 == 0:
            count2 += 1
            tmp //= 2
        else:
            break
    while count5 < 18:
        if tmp % 5 == 0:
            count5 += 1
            tmp //= 5
        else:
            break
    for i in range(18-count2,19):
        for j in range(18-count5,19):
            ans += a[i][j]
    a[count2][count5] += 1
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
for i in range(M):
    ans = int(A[0] / 2)
    A[0] = ans
    A = sorted(A, reverse=True)
sum = 0
for a in A:
    sum += a
print(sum)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import heapq
N, M = map(int, input().split())
A = list(map(int, input().split()))
sum = 0
l = []
for i in A:
    heapq.heappush(l, i*-1)
for i in range(M):
    c = int(heapq.heappop(l)*-1/2)
    heapq.heappush(l, c*-1)
for a in l:
    sum += a*-1
print(sum)
### BUGGY CODE ###

import sys
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
BC = [list(map(int, sys.stdin.readline().split())) for i in range(Q)]
for i in range(Q):
    B, C = BC[i]
    A[A == B] = C
    print(sum(A))

### FIXED CODE ###

import sys
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Co = Counter(A)
Q = int(input())
BC = [list(map(int, sys.stdin.readline().split())) for i in range(Q)]
ans = sum(A)
for i in range(Q):
    B, C = BC[i]
    ans += ((C - B) * Co[B])
    print(ans)
    Co[C] += Co[B]
    Co[B] = 0
### BUGGY CODE ###

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

idx = B[0]
idx_count = 0
idx_set = []
for i in range(N):
  if idx != B[i]:
    tmp1 = int(idx_count*(idx_count-1)/2)		# 同一の整数を持つボールの組合せ数
    tmp2 = int((idx_count-1)*(idx_count-2)/2)	# 同一の整数を持つボールを1つ除いたときの組合せ数
    idx_set.append([idx, tmp1, tmp2])
    idx_count = 0
    idx = B[i]
  idx_count+=1
if idx_count != 0:
  tmp1 = int(idx_count*(idx_count-1)/2)			# 同一の整数を持つボールの組合せ数
  tmp2 = int((idx_count-1)*(idx_count-2)/2)		# 同一の整数を持つボールを1つ除いたときの組合せ数
  idx_set.append([idx, tmp1, tmp2])
#print(idx_set)
idx_sum_set = []
all_c = 0
for i in range(len(idx_set)):
  all_c += idx_set[i][1]
for i in range(len(idx_set)):
  tmp = all_c-idx_set[i][1]+idx_set[i][2]
  idx_sum_set.append([idx_set[i][0], tmp])    

if len(idx_sum_set) == 1:
  for i in range(N):
    print(idx_sum_set[0][1])
else:
  for i in range(N):
    j = int(len(idx_sum_set)/2)
    while 1:
      if A[i] == idx_sum_set[j][0]:
        print(idx_sum_set[j][1])
        break
      elif A[i] > idx_sum_set[j][0]:
        j = j + int((len(idx_sum_set)-j)/2)
      elif A[i] < idx_sum_set[j][0]:
        j = int(j/2)



### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = np.zeros(N+1)

for i in range(N):
  B[A[i]]+=1
#print(B)

all_c = 0
for i in range(1,N+1):
  all_c += int(B[i]*(B[i]-1)/2)			# 同一の整数を持つボールの組合せ数
for i in range(N):
  if B[A[i]] != 0:
    print(int(all_c-(B[A[i]]-1)))
### BUGGY CODE ###

MOD = 1000000007
# 二項係数
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD

com = COM(100000, MOD)
n, k = map(int, input().split())
a_list = sorted(list(map(int, input().split())))
 
ans = 0
for i in range(len(a_list) - k + 1):
    for j in range(len(a_list) - 1, k + i - 2, -1):
        if(a_list[j] - a_list[i] != 0):
            ans += (a_list[j] - a_list[i]) * com.calc_COM(j-i-1, k-2)
ans %= 1000000007
print(ans)

### FIXED CODE ###

MOD = 1000000007
# 二項係数
class COM():
    def __init__(self, MAX, MOD):
        self.MOD = MOD
        self.MAX = MAX
        self.fac = [1] * MAX
        self.finv = [1] * MAX
        inv = [1] * MAX
        for i in range(2, MAX):
            self.fac[i] = self.fac[i - 1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            self.finv[i] = self.finv[i - 1] * inv[i] % MOD
    def calc_COM(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        if self.MAX <= n:
            return 0
        return self.fac[n] * (self.finv[k] * self.finv[n - k] % self.MOD) % self.MOD

com = COM(100000, MOD)
n, k = map(int, input().split())
a_list = sorted(list(map(int, input().split())))

ans = 0
if k == 1:
    print(0)
else:
    for i in range(1, n+1):
        if i >= k:
            ans += a_list[i-1] * com.calc_COM(i-1, k-1)
        if n-i >= k-1:
            ans -= a_list[i-1] * com.calc_COM(n-i, k-1)
    ans %= MOD
    print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
h = [int(x) for x in input().split()]
a = []
b = []
for i in range(m):
    aa, bb = map(int, input().split())
    a.append(aa)
    b.append(bb)

path = [[] for i in range(n)]
for i in range(m):
    for j in range(1, n+1):
        if a[i] == j:
            path[j-1].append(b[i])
        if b[i] == j:
            path[j-1].append(a[i])

#print('h: ', h)
#print(path)

total = 0
for i in range(n):
    flag = 1
    #print('len(path[i]): ', len(path[i]))
    for j in range(len(path[i])):
        idx = path[i][j]
        #print('idx: ',idx)
        #print('h[idx]:',h[idx])
        #print('h[i]:', h[i])
        if h[idx-1] >= h[i]:
            flag = 0
    total += flag

print(total)


### FIXED CODE ###

n, m = map(int, input().split())
h = [int(x) for x in input().split()]

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

for i in range(m):
    a, b = map(int, input().split())
    if h[a-1] >= h[b-1]:
        ans[b-1] = 0
    if h[b-1] >= h[a-1]:
        ans[a-1] = 0

count = ans.count(1)
print(count)
### BUGGY CODE ###

n=int(input())
s=list(input())
q=int(input())
k=list(map(int,input().split()))
h=[0]*q
di=s.count("D")
for r in range(di):
    f=s.index("D")
    s=s[f+1:]
    a=0
    l=0
    sp=min(len(s),max(k))
    for c in range(sp):
        if s[c]=="M":
            a+=1
        elif s[c]=="C":
            l+=a
        if c+2 in k:
            h[k.index(c+2)]+=l
    else:
        for i in k:
            if i>len(s)+1:
                h[k.index(i)]+=l 
for i in range(q):
    print(h[i])

### FIXED CODE ###

n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

# W分の配列を用意、全Wに対してVが最大になるものを見つける
N,W=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(N)]

dp=[-1]*(W+1)
dp[0]=0
for i in range(N):
  w,v=WV[i]
  for j in range(W-w,-1,-1): # 逆順じゃないと同じものを二つ選べる
    if dp[j]!=-1:
      dp[j+w]=max(dp[j+w],dp[j]+v)
print(max(dp))

### FIXED CODE ###

import numpy as np
n,w=map(int,input().split())
WV=[list(map(int,input().split())) for _ in range(n)]

dp=np.zeros(w+1,int)
for i in range(n):
  w,v=WV[i]
  dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])
### BUGGY CODE ###


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(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)


### FIXED CODE ###


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(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)
### BUGGY CODE ###

N, M = map(int, input().split())

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

ls = []

res = []

for m in range(M):
    ls.append(list(map(int, input().split())))

for n in range(N):
    tmp_res = 1
    for l in ls:
        if n + 1 in l:
            if n + 1 == l[0]:
                if H[n] <= H[l[1] - 1]:
                    tmp_res = 0
            else:
                if H[n] <= H[l[0] - 1]:
                    tmp_res = 0
    res.append(tmp_res)


print(sum(res))

### FIXED CODE ###

N, M = map(int, input().split())

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

ls = [1 for _ in range(N)]

for m in range(M):
    A, B = map(int, input().split())

    if ls[A - 1]: 
        ls[A - 1] = 0
        if H[A - 1] > H[B - 1]:
            ls[A - 1] = 1

    if ls[B - 1]: 
        ls[B - 1] = 0
        if H[B - 1] > H[A - 1]:
            ls[B - 1] = 1


print(sum(ls))
### BUGGY CODE ###

all,rolls=map(int,input().split())
List=list(map(int,input().split()))

sum = 0
sumList =[]

for i in range(all - rolls + 1):
	all_sum = 0
	for j in range(rolls):
		sum = (List[i + j] + 1) / 2
		all_sum = all_sum + sum
	sumList.append(all_sum)

sumList.sort(reverse=True)
print(sumList[0])



### FIXED CODE ###

all,rolls=map(int,input().split())
inputList=list(map(int,input().split()))

sum = 0
sumList =[]

# 初めに全期待値計算
for i in range(all):
	inputList[i] = (inputList[i] + 1) / 2

# 最初の組み合わせの期待値計算
for i in range(rolls):
	sum = sum + inputList[i]
sumList.append(sum)

# 2番目以降の期待値計算
for i in range(all - rolls):
	sum = sum + inputList[i + rolls] - inputList[i]
	sumList.append(sum)

sumList.sort(reverse=True)
print(sumList[0])