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

import bisect

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

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

l=0
r=len(A)
c=(r+l)/2

n=0


for i in B:
    cnt=0
    if i in A and cnt==0:
        n+=1
        cnt+=1
    elif i>c:
        l=c+1
        c=(r+l)/2
    else:
        r=c
        c=(r+l)/2

print(n)



### FIXED CODE ###


def bs(A, n):
    l=0
    r=len(A)
    while l<r:
        mid=int((l+r)/2)
        if A[mid]==n:
            return mid
        else:
            if n<A[mid]:
                r=mid
            else:
                l=mid+1

    return -1

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

T=int(input())
B=[int(j) for j in input().split()]

A.sort()

cnt=0
for i in range(T):
    x=bs(A,B[i])
    if x!=(-1):
        cnt=cnt+1

print(cnt)
### BUGGY CODE ###

import math
from itertools import combinations
import sys
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
  
def is_prime(x):
    if x < 2: return False # 2未満に素数はない
    if x == 2 or x == 3 or x == 5: return True # 2,3,5は素数
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0: return False # 2,3,5の倍数は合成数

    # ためし割り: 疑似素数(2でも3でも5でも割り切れない数字)で次々に割っていく
    prime = 7
    step = 4
    while prime <= math.sqrt(x):
        if x % prime == 0: return False

        prime += step
        step = 6 - step

    return True
  
prime_nums = primes(55555)
prime_list = prime_nums[:5]
prime_remain = prime_nums[5:]
N = int(input())
for p in prime_remain:
  prime_l = prime_list + [p]
  combs = list(combinations(prime_l, 5))
  if not True in [is_prime(sum(c)) for c in combs]:
    prime_list = [p for p in prime_l]
  
  # print(len(prime_list), p)
  if len(prime_list) == N:
    for p in prime_list:
      print(p, end = ' ')
    break
    # sys.exit()

### FIXED CODE ###

import math

def primes(x):
    if x < 2: return []
 
    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない
 
    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0
 
    return [prime for prime in primes if prime != 0]
  
n = int(input())
prime_nums = primes(55555)
ans = []
for p in prime_nums:
  if str(p)[-1] == '1':
    ans.append(p)
  if len(ans) == n:
    for a in ans:
      print(a, end = ' ')
    quit()
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
    count = 0
    B =[]
    for j in range(len(A)):
        if A[j]==i:
            count += 1
        else:
            B.append(A[j])
    print(count)
    A = B

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [0]*N
for i in range (len(A)):
    B[A[i]-1] +=1
print('\n'.join(map(str, B)))
### BUGGY CODE ###

import collections

def main():
    n = int(input())
    c = [[] for i in range(n)]
    count = 0
    for num,i in enumerate(c):
        c[num] = collections.Counter(input())

    for i in range(n):
        for j in range(i+1,n):
            if c[i] == c[j]:
                count = count + 1

    print(count)


if __name__ == '__main__' :
    main()

### FIXED CODE ###

from collections import Counter

n = int(input())
count = 0
lists =[]
count_dict = Counter()

for i in range(n):
    input_data = ''.join(sorted(input()))
    if input_data in count_dict:
        count += count_dict[input_data]
        count_dict[input_data] += 1
    else:
        count_dict[input_data] = 1

print(count)
### BUGGY CODE ###

ii=lambda:map(int,raw_input().split())
n,k=ii()
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=ii()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
cost=[0]*n
ans=10**5
def dfs(x,f):
    if f>=0:vis[f]=True
    q=[(x,0)]
    while len(q):
        v,c=q.pop(0)
        if c>k/2:break
        cost[v]=c;vis[v]=True
        for w in e[v]:
            if not vis[w]:q+=[(w,c+1)]
    return n-vis.count(True)
if k%2:
    for i in range(n):
        for j in e[i]:
            if i<j:vis=[False]*n;dfs(i,j);ans=min(ans,dfs(j,i))
    print ans
else:
    for i in range(n):vis=[False]*n;ans=min(ans,dfs(i,-1))
    print ans


### FIXED CODE ###

ii=lambda:map(int,raw_input().split())
n,k=ii()
T,F=True,False
e=[[] for _ in range(n)]
for _ in range(n-1):
    a,b=ii()
    e[a-1]+=[b-1];e[b-1]+=[a-1]
cost=[0]*n
ans=10**5
def dfs(x,f):
    if f>=0:vis[f]=T
    q=[(x,0)]
    while len(q):
        v,c=q.pop(0)
        if c>k/2:break
        cost[v]=c;vis[v]=T
        for w in e[v]:
            if not vis[w]:q+=[(w,c+1)]
    return n-vis.count(T)
if k%2:
    for i in range(n):
        for j in e[i]:
            if i<j:vis=[F]*n;dfs(i,j);ans=min(ans,dfs(j,i))
else:
    for i in range(n):vis=[F]*n;ans=min(ans,dfs(i,-1))
print ans
### BUGGY CODE ###

n = int(input())
a = [int(x) for x in input().split()]

a.append(0)
tmp = 0
ans = 0

for i in range(n):
    for y in range(n+1):
        if i == y:
            pass
        else:
            ans += abs(a[y] - tmp)
            tmp = a[y]
    print(ans)
    tmp = 0
    ans = 0

### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]

a.append(0)
a.insert(0,0)

ans = 0

for i in range(1,n+2):
    ans += abs(a[i-1]-a[i])

for i in range(1,n+1):
    print(ans + abs(a[i-1] - a[i+1]) - (abs(a[i] - a[i-1]) + abs(a[i] - a[i+1])))
### BUGGY CODE ###

s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
for i in range(n1,-1,-1):
    for j in range(n2,-1,-1):
        if i==n1 or j==n2:
            dp[i][j]=""
        else:
            if s1[i]==s2[j]:
                dp[i][j]=s1[i]+dp[i+1][j+1]
            else:
                x=dp[i][j+1]
                y=dp[i+1][j]
                if len(x)>len(y):
                    dp[i][j]=x
                else:
                    dp[i][j]=y
print(dp[0][0])

### FIXED CODE ###

s1=input()
s2=input()
n1,n2=len(s1),len(s2)
dp=[[-1 for j in range(n2+1)] for i in range(n1+1)]
for i in range(n1,-1,-1):
    for j in range(n2,-1,-1):
        if i==n1 or j==n2:
            dp[i][j]=0
        else:
            if s1[i]==s2[j]:
                dp[i][j]=1+dp[i+1][j+1]
            else:
                dp[i][j]=max(dp[i][j+1],dp[i+1][j])
n=""
i,j=0,0
while i<n1 and j<n2:
    if dp[i][j]==dp[i+1][j]:
        i+=1
    elif dp[i][j]==dp[i][j+1]:
        j+=1
    else:
        n+=s1[i]
        i+=1
        j+=1
print(n)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peer_nodes = [[] for _ in range(N)]
edge_colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peer_nodes[a].append(b)
    if not a in peer_nodes[b]:
        peer_nodes[b].append(a)
    edge_colors[a][b] = 0

#print(peer_nodes,edge_colors)

def draw_color_return_max_colors(node):
    max_colors = 0
    peers = peer_nodes[node]
    if len(peers) == 0:
        return 0
    used_colors = []
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        c = edge_colors[i][j]
        if c != 0:
            used_colors.append(c)
    #print('----', node, peers,used_colors)
    if len(used_colors) == len(peers):
        return 0
    color = 1
    for p in peers:
        if node<p:
            i,j = node,p
        else:
            i,j = p,node
        if edge_colors[i][j] > 0:
            continue
        else:
            while(color in used_colors):
                color += 1
            if edge_colors[i][j] == 0:
                used_colors.append(color)
                edge_colors[i][j] = color
    max_colors = max(used_colors)
    for p in peers:
        max_colors = max(max_colors, draw_color_return_max_colors(p))

    return max_colors


print(draw_color_return_max_colors(pairs[0][0]))

for a,b in pairs:
    print(edge_colors[a][b])


### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
#import bisect
#from collections import deque
import math

sys.setrecursionlimit(10**5)

def input():
    return sys.stdin.readline().rstrip('\n')

N = int(input())
peers = [[] for _ in range(N)]
colors = [{} for _ in range(N)]
pairs = []
for _ in range(N-1):
    a,b = list(map(int, input().split()))
    a -= 1
    b -= 1
    pairs.append([a,b])
    peers[a].append(b)
    colors[a][b] = 0


def draw(node, parent_edge_color):
    _peers = peers[node]
    if len(_peers) == 0:
        return 0
    color = 1
    max_nrof_color = 1
    for peer in _peers:
        #print(node,peer,color)
        if color == parent_edge_color:
            color +=1
        colors[node][peer] = color
        max_nrof_color = max(max_nrof_color, color, draw(peer, color))
        color += 1

    return max_nrof_color


print(draw(0,0))
for a,b in pairs:
    print(colors[a][b])
### BUGGY CODE ###

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

#辞書dの0でない要素の数を返す関数
def count_dict(d):
    list = d.values()
    cnt_dict = 0
    for i in list:
        if i == 0:
            cnt_dict += 1
    return len(d) - cnt_dict

dict = {}
for i in a_n:
    if i in dict:
        dict[i] += 1
    else:
        dict[i] = 1

cnt = 0
while count_dict(dict) > K:
    minimum = 100000000
    flag = False
    for i in dict.values():
        if i <= minimum and i != 0:
            minimum = i
    for j in dict:
        if dict[j] == minimum:
            dict[j] = 0
            cnt += minimum
            flag = True
        if flag == True:
            break
print(cnt)

### FIXED CODE ###

import collections

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

dict = collections.Counter(a_n)

v_list = list(dict.values())
v_list_s = sorted(v_list)

cnt = 0
if len(v_list_s) <= K:
    print(0)
else:
    x = len(v_list_s) - K
    for i in range(x):
        cnt += v_list_s[i]
    print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
date = []
salary = []
for _ in range(N):
  a, b = map(int, input().split())
  date.append(a)
  salary.append(b)
sum_salary = 0
for i in range(1, M+1):
  max_salary = 0
  index = -1
  for j in range(len(date)):
      if date[j] <= i:
        if max_salary < salary[j]:
          max_salary = salary[j]
          index = j
  sum_salary += max_salary
  if index >= 0:
    date.pop(index)
    salary.pop(index)
print(sum_salary)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
jobs = [[] for i in range(M)]

for i in range(N):
  a, b = map(int, input().split())
  if a > M:
    continue
  jobs[M-a].append(b)
sum_salary = 0
h=[]
for i in range(M-1, -1, -1):
  for b in jobs[i]:
    heapq.heappush(h,-b)
  if(len(h)!=0):
    a = -heapq.heappop(h)
    sum_salary += a
print(sum_salary)
### BUGGY CODE ###

H,N = map(int,input().split())
magic = [list(map(int,input().split())) for i in range(N)]

INF = 10**10
#print(magic)

AM = 0
for i in range(N):
    AM = max(AM,magic[i][0])
#print(AM)


dp = [INF for i in range(H+AM+1)]
dp[0] = 0

for i in range(1,H+AM+1):
    for j in range(N):
        if magic[j][0] > i:
            dp[i] = min(dp[i],magic[j][1])
        else:
            dp[i] = min(dp[i-magic[j][0]]+magic[j][1],dp[i])
ans = INF
for i in range(H,H+AM+1):
    ans = min(ans,dp[i])
print(ans)



### FIXED CODE ###

H,N = map(int,input().split())
magic = [list(map(int,input().split())) for i in range(N)]

INF = 10**10
#print(magic)

AM = 0
for i in range(N):
    AM = max(AM,magic[i][0])
#print(AM)


dp = [INF for i in range(H+AM+1)]
dp[0] = 0

for i in range(1,H+AM+1):
    for j in range(N):
        if magic[j][0] > i:
            dp[i] = min(dp[i],magic[j][1])
        else:
            dp[i] = min(dp[i-magic[j][0]]+magic[j][1],dp[i])
ans = INF
for i in range(H,H+AM+1):
    ans = min(ans,dp[i])
print(ans)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 1

for _a in a:
    ans *= _a

if ans > 10**18:
    ans = -1

if 0 in a:
    ans = 0
print(ans)

### FIXED CODE ###

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

ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        ans = -1
        break

if 0 in A:
    ans = 0

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

h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print(min(DP[h:]))

### FIXED CODE ###

h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print(min(DP[h:]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque

S = input().rstrip()
Q = int(input())
Query = []

for _ in range(Q):
    Query.append(input().rstrip().split())

for i in Query:
    if i[0] == "1":
        S = S[::-1]
    elif i[1] == "1":
        S = i[2] + S
    else:
        S += i[2]
print(S)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque

S = deque(list(input().rstrip()))
Q = int(input())
Query = []

flag = 0

for _ in range(Q):
    Query.append(input().rstrip().split())

for i in Query:
    if i[0] == "1":
        flag += 1
    elif i[1] == "1":
        if flag % 2 == 0:
            S.appendleft(i[2])
        else:
            S.append(i[2])
    else:
        if flag % 2 == 0:
            S.append(i[2])
        else:
            S.appendleft(i[2])
if flag % 2 == 0:
    print("".join(list(S)))
else:
    print("".join(list(S))[::-1])
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class SparseTable:
    def __init__(self, aa):
        w = len(aa)
        h = w.bit_length()
        table = [aa] + [[-1] * w for _ in range(h - 1)]
        tablei1 = table[0]
        for i in range(1, h):
            tablei = table[i]
            for j in range(w-(1<<i)+1):
                rj = j + (1 << (i - 1))
                tablei[j] = tablei1[j]|tablei1[rj]
            tablei1 = tablei
        self.table = table

    def val(self, l, r):
        i = (r - l).bit_length() - 1
        tablei = self.table[i]
        L = tablei[l]
        R = tablei[r - (1 << i)]
        return L|R

n,q=MI()
cc=MI()
aa=[set([c]) for c in cc]
sp=SparseTable(aa)
for _ in range(q):
    l,r=MI()
    print(len(sp.val(l-1,r)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

    def add(self, i, x):
        i += 1
        while i < self.n:
            self.table[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

n,q=MI()
cc=LI()
lri=[]
mx=500005
#mx=10
for i in range(q):
    l,r=MI()
    l-=1
    lri.append((l,r-1,i))

lri.sort(key=lambda x:x[1])

#print(lri)
last=[-1]*mx
st=BitSum(mx)
ans=[0]*q
now=0
for l,r,i in lri:
    for j in range(now,r+1):
        c=cc[j]
        pre=last[c]
        if pre!=-1:st.add(pre,-1)
        last[c]=j
        st.add(j,1)
    #print(l,r,st.tree,last)
    now=r+1
    ans[i]=st.sum(r)-st.sum(l-1)
print(*ans,sep="\n")
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
M=1
A.sort()
for j in A:
	M=M*j
	if M>10**18:
		M=-1
	if M ==0:
		M=0
		break
print(M)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
M=1
A.sort()
if A[0]==0:
	M=0
else:
	for j in A:
		M=M*j
		if M>10**18:
			M=-1
			break
print(M)
### BUGGY CODE ###

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

dp = [0] * (K + 1)
ans = 0
for k in range(K, 0, -1):
    num = K // k
    dp[k] = pow(num, N)
    for n in range(2, num+1):
        if n*k <= K:
            dp[k] -= dp[n*k]
            dp[k] %= MOD

    ans += dp[k] * k % MOD
    ans %= MOD

print(ans)

### FIXED CODE ###

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

dp = [0] * (K + 1)
ans = 0
for k in range(K, 0, -1):
    num = K // k
    dp[k] = pow(num, N, MOD)
    for n in range(2, num+1):
        if n*k <= K:
            dp[k] -= dp[n*k]
            dp[k] %= MOD

    ans += dp[k] * k % MOD
    ans %= MOD

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

s = input().strip()
N = len(s)
K = int(input())
Ind = {chr(i):[] for i in range(97,123)}
for i in range(N):
    Ind[s[i]].append(i)
C = {}
cnt = 0
flag = 0
for j in range(97,123):
    for ind in Ind[chr(j)]:
        for i in range(ind+1,N+1):
            if s[ind:i] not in C:
                C[s[ind:i]] = 1
                cnt += 1
    if cnt>=K:break
A = sorted(list(C.keys()))
print(A[K-1])

### FIXED CODE ###

S = input().strip()
N = len(S)
K = int(input())
A = []
for k in range(1,min(6,N+1)):
    for i in range(N-k+1):
        x = S[i:i+k]
        if x not in A:
            A.append(x)
A = sorted(A)
print(A[K-1])
### BUGGY CODE ###


N,K=map(int,input().split())
a=list(map(int,input().split()))
tmp=10**-10
l=[]
for i in range(N-K+1):
  s=sum(a[i:i+K])
  if s>tmp:
    l=a[i:i+K]
    tmp=s

ans=(tmp+K)/2
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
s=[0]
for i in range(n):
  s.append(a[i]+s[-1])
for i in range(n-k+1):
  tot=s[i+k]-s[i]
  ans=max((tot+k)/2,ans)
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*len(s)
for i in range(len(s)-1):
    if s[i]=="A" and s[i+1]=="C":
        t[i+1]=t[i]+1
    else:
        t[i+1]=t[i]+0
for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

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

s=input()
s = list(s)
if s[0] == '0':
    count0 = 1
else:
    count0 = 0

memo = []
ans = 0
a = ''
for i in range(len(s)):
    #print(i)
    memo.append(s[i])
    ans = max(ans, len(memo))
    if i<n-1:
        if s[i] == '1' and s[i+1] == '0':
            count0 += 1
            if count0 == k+1:
                while True:
                    a = memo.pop(0)
                    if a == '0' and memo[0] == '1':
                        count0 = k
                        break
print(ans)
    

### FIXED CODE ###

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

s=input()
s = list(map(int,s))

memo = [0]

for i in range(1,n):
    if s[i-1] != s[i]:
        memo.append(i)

ans = 0
for i in range(len(memo)):
    start = memo[i]
    if (s[start] == 1):
        end = i + 2*k +1
    else:
        end = i + 2*k
    if end < len(memo):
        end = memo[end]
    else:
        end = len(s)
    ans = max(ans, end-start)
print(ans)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
ans = 0
for i in range(n):
    for j in range(i, n):
        if a[i] + a[j] == abs(i - j):
            ans += 1
print(ans)

### FIXED CODE ###

import collections

n = int(input())
a = [int(i) for i in input().split()]
a_i = [i - aa for i, aa in enumerate(a)]
a_j = [j + aa for j, aa in enumerate(a)]

ci = collections.Counter(a_i)
cj = collections.Counter(a_j)
ans = 0
for item, value in ci.items():
    if item in cj.keys():
        ans += cj[item] * ci[item]
print(ans)
### BUGGY CODE ###


import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


# def init(n_):
#     #簡単にするために2のべき乗に揃える
#     n = 1
#     while n <= n_:
#         n *= 2
#     return n

#初期化
N = int(input())
n = 1
while n <= N:
    n *= 2

data = [0] * (2 * n - 1)

def update(k, a):
    k += n - 1
    data[k] = a
    while k > 0:
        data[k] = max(a, data[k])
        k = (k - 1) // 2
        # data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        v1 = query(a, b, 2 * k + 1, l, (l + r)//2)
        v2 = query(a, b, 2 * k + 2, (l + r)//2, r)
        return max(v1, v2)

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

# ans = 0
for i in range(N):
    # h = int(input())
    # a = int(input())
    h = H[i]
    a = A[i]
    tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(h, tmp + a)
    # ans = max(ans, tmp + a)
    # print (data)

print (query(1, N + 1))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

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

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0

tmp = 0
for i in range(n):
    tmp += sum(range(1, p[i] + 1)) / p[i]
    if i >= k:
        tmp -= sum(range(1, p[i - k] + 1)) / p[i - k]
    ans = max(ans, tmp)

print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
e = [sum(range(1, pi + 1)) / pi for pi in p]

tmp = 0
for i in range(n):
    tmp += e[i]
    if i >= k:
        tmp -= e[i - k]
    ans = max(ans, tmp)

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

N = int(input())
S = str(input())
P = 0
for i in range(0,N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if(S[i] != S[j] and S[i] != S[k] and S[j] != S[k] and j-i != k-j):
                P += 1
print(P)

### FIXED CODE ###

N = int(input())
S = str(input())
P = 0
R = S.count('R')
G = S.count('G')
B = S.count('B')
P = R*G*B
for i in range(1,(N//2)+1):
    for j in range(N-2*i):
            if S[j]!=S[j+i] and S[j+i]!=S[j+2*i] and S[j]!=S[j+2*i]:
                P -= 1
print(P)