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

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**10, N)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])

@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        vs = []
        ws = []
        while V >= n:
            vs.append(vws[V][0])
            ws.append(vws[V][1])
            V = (V-1) // 2
        print(func(np.array(vs, np.int32), np.array(ws, np.int32), L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

from bisect import bisect_left
from collections import defaultdict

N = int(input())

A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
num_a = 0
num_c = 0
res = 0
pre_b = -1

dict_C = defaultdict(int)

for b in B:
    dict_C[b] = C.count(b)


for b in B:
    if b == pre_b:
        res += num_a * num_c
        continue
    num_a = bisect_left(A, b) # a < b となるAの要素数
    pre_num_c = bisect_left(C, b)
    num_c = N - pre_num_c # c > b となるAの要素数
    if pre_num_c != N and C[pre_num_c] == b:
        num_c -= dict_C[b]
    res += num_a * num_c
    pre_b = b
print(res)



### FIXED CODE ###

from bisect import bisect_left
from collections import defaultdict

N = int(input())

A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))
num_a = 0
num_c = 0
res = 0
pre_b = -1

dict_C = defaultdict(int)


for b in B:
    if b == pre_b:
        res += num_a * num_c
        continue
    num_a = bisect_left(A, b) # a < b となるAの要素数
    pre_num_c = bisect_left(C, b)
    num_c = N - pre_num_c # c > b となるAの要素数
    if pre_num_c != N and C[pre_num_c] == b:
        num_c = N - bisect_left(C, b+1)
    res += num_a * num_c
    pre_b = b
print(res)
### BUGGY CODE ###

N = int(input())
S = input().strip()
cmax = 0
for k in range(1,N//2+1):
    C = {}
    for i in range(N-k+1):
        x = S[i:i+k]
        if x not in C:
            C[x]=[]
        C[x].append(i)
    for a in C:
        if len(C[a])>1 and C[a][-1]-C[a][0]>=k:
            cmax = max(cmax,k)
            break
print(cmax)

### FIXED CODE ###

N = int(input())
S = input().strip()
cmax = 0
for k in range(1,N):
    X = S[:N-k]
    Y = S[k:]
    cur = 0
    cnt = 0
    for i in range(N-k):
        if X[i]!=Y[i]:
            cmax = max(cmax,min(cnt,k))
            cur = i
            cnt = 0
        else:
            cnt += 1
    cmax = max(cmax,min(cnt,k))
print(cmax)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
  ans += sum(a[i])

memo = {}
for i in range(n):
  memo[i] = {}
for k in range(n):
  for i in range(n):
    for j in range(n):
      if k != i and i != j and j != k :
        if a[i][j] > a[i][k]+a[k][j]:
          print(-1)
          exit()
        elif a[i][j] == a[i][k]+a[k][j]:
          if j not in memo[i]:
            ans -= a[i][j]
            memo[i][j] = 1
                  
print(ans//2)

#プリム法
#mincost = [float("inf")]*n
#used = [False]*n
#mincost[0] = 0
#res = 0
#
#while True:
#  v = -1
#  for u in range(n):
#    if (not used[u]) and (v == -1 or mincost[u] < mincost[v]):
#      v = u
#  if v == -1:
#    break
#  used[v] = True
#  res += mincost[v]
#  for u in range(n):
#    mincost[u] = min(mincost[u],a[v][u])

### FIXED CODE ###

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

ans = 0
for i in range(n):
  ans += sum(a[i])

memo = {}
for i in range(n):
  memo[i] = {}
for k in range(n):
  for i in range(n):
    for j in range(n):
      if k != i and i != j and j != k :
        if a[i][j] > a[i][k]+a[k][j]:
          print(-1)
          exit()
        elif a[i][j] == a[i][k]+a[k][j]:
          if j not in memo[i]:
            ans -= a[i][j]
            memo[i][j] = 1
                  
print(ans//2)

#プリム法
#mincost = [float("inf")]*n
#used = [False]*n
#mincost[0] = 0
#res = 0
#
#while True:
#  v = -1
#  for u in range(n):
#    if (not used[u]) and (v == -1 or mincost[u] < mincost[v]):
#      v = u
#  if v == -1:
#    break
#  used[v] = True
#  res += mincost[v]
#  for u in range(n):
#    mincost[u] = min(mincost[u],a[v][u])
### BUGGY CODE ###

import copy
import math
import time
import statistics
import math
import itertools
import bisect

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():
    start = time.time()
    n = get_int()

    a_list = get_int_list()
    b_list = get_int_list()
    c_list = get_int_list()

    a_list.sort()
    b_list.sort()
    c_list.sort()

    a_count = []
    b_count = []

    idx = 0
    for a in a_list:
        idx = bisect.bisect_right(b_list, a, idx)
        a_count.append(idx)

    idx = 0
    for b in b_list:
        idx = bisect.bisect_right(c_list, b, idx)
        b_count.append(idx)

    ans = 0
    for a in a_count:
        if a == n:
            continue
        for i in range(a, n):
            ans += n - b_count[i]

    print(ans)
    #print(time.time() - start)

if __name__ == '__main__':
    main()




### FIXED CODE ###

import copy
import math
import time
import statistics
import math
import itertools
import bisect

# a = get_int()
def get_int():
    return int(input())
# a = get_string()
def get_string():
    return input()
# a_list = get_int_list()
def get_int_list():
    return [int(x) for x in input().split()]
# a_list = get_string_list():
def get_string_list():
    return input().split()
# a, b = get_int_multi()
def get_int_multi():
    return map(int, input().split())
# a_list = get_string_char_list()
def get_string_char_list():
    return list(str(input()))
# print("{} {}".format(a, b))
# for num in range(0, a):
# a_list[idx]
# a_list = [0] * a
'''
while (idx < n) and ():

    idx += 1
'''

def main():
    start = time.time()
    n = get_int()

    a_list = get_int_list()
    b_list = get_int_list()
    c_list = get_int_list()

    a_list.sort()
    b_list.sort()
    c_list.sort()

    a_count = []
    b_count = []
    b_count2 = []

    idx = 0
    for a in a_list:
        idx = bisect.bisect_right(b_list, a, idx)
        a_count.append(idx)

    idx = 0
    for b in b_list:
        idx = bisect.bisect_right(c_list, b, idx)
        b_count.append(idx)

    ruikei = 0
    for i in range(n-1, -1, -1):
        ruikei += n - b_count[i]
        b_count2.append(ruikei)

    b_count2.sort(reverse=True)

    ans = 0
    for a in a_count:
        if a == n:
            continue
        ans += b_count2[a]

    print(ans)
    #print(time.time() - start)

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

def combinations(R, G, B, N):
    R, G, B, N = int(R), int(G), int(B), int(N)
    number_combos = 0
    
    for x in range(N + 1):
        N_modified_x = N - R * x
        for y in range(N_modified_x + 1):
            N_modified_y = N_modified_x - G * y
            for z in range(N_modified_y + 1):
                if B * z == N_modified_y:
                    number_combos += 1
    return number_combos

print(combinations(13, 1, 4, 3000))

### FIXED CODE ###

def combinations(R, G, B, N):
    R, G, B, N = int(R), int(G), int(B), int(N)
    sorted_tuple = sorted((R, G, B), reverse=True)
    R = sorted_tuple[0]
    G = sorted_tuple[1]
    B = sorted_tuple[2]
    number_combos = 0

    for x in range(N // R + 1):
        for y in range((N - R * x) // G + 1):
            if (N - R * x - G * y) % B == 0:
                number_combos += 1
        
    return number_combos

R, G, B, N = input().split(' ')
print(combinations(R, G, B, N))
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()]
ans = []
for i in range(N):
  ans.append(A.index(max(A)) + 1)
  A[A.index(max(A))] = 0
ans.reverse()
for i in range(N):
  print(ans[i], end = " ")

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()]
ans = [0] * N
for i in range(N):
  ans[A[i] - 1] = i + 1
print(*ans)
### BUGGY CODE ###


import heapq
import collections
N =  int(input())
nums = list(map(int,input().split(" ")))
keta = [0 for _ in range(61)]
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = [1]
MOD = 10 ** 9 + 7
for i in range(60):
    temp = jijou[i] * 2
    temp%= MOD
    jijou.append(temp)

for num in nums:
    s = format(num,"b")
    l = len(s)
    for i in range(0,l):
        keta[i] += int(s[l - i - 1 ])
ans = 0
for j,num in  enumerate(nums[:-1]):
    s = format(num, "b")
    l = len(s)
    for i in range(0,61): #i →  2 ** i 乗 桁目に対応
        if l <= i:
            ans += (keta[i] * jijou[i]) % MOD
        else:
            if s[l - i - 1 ] == "0":
                ans += (keta[i] * jijou[i]) % MOD
            else:
#              (N - j + 1) - (keta[i] + 1 ) → 0が経っているところの個数
                ans += (( (N - j + 1) - (keta[i] + 1)  ) * ( jijou[i]) ) % MOD
                keta[i] -= 1


print(ans % MOD)

### FIXED CODE ###


import heapq
import collections
import math
import sys
N =  int(input())
input = sys.stdin.readline
# num = a << b →  a  * (2 ** b)
# 1 << i → i桁目のマスク
# mask = 1 << i
# num = a << b
# num & mask


#
nums = list(map(int,input().split(" ")))
keta = [0] * 62
# ある桁の1の出現回数
# keta[k] → 2**k の桁
jijou = []
MOD = 10 ** 9 + 7


for num in nums:
    s = format(num,"b")
    l = len(s)

    for i in range(0,l):
        if s[l - i - 1 ] == "1":
            keta[i] += 1

ans = 0
temp = 1
for i in range(62):

    ans += ( keta[i] * (N - keta[i])) * temp
    ans %= MOD
    temp *= 2
    temp %= MOD
print(ans)
### BUGGY CODE ###

import numpy as np

N=int(input())
A=list(map(int,input().split()))
Adic={}
for i in A:
  if Adic.get(i)==None:
    Adic[i]=1
  else:
    Adic[i]+=1
Q=int(input())
ope=[]

for i in range(Q):
  ope.append(list(map(int,input().split())))

A=np.array(A)

for b,c in ope:
  if Adic.get(b)!=None:
    if Adic.get(c)==None:Adic[c]=0
    Adic[c]+=Adic.pop(b)
  sum=0
  for key,value in Adic.items():
    sum+=key*value
  print(sum)

### FIXED CODE ###

import numpy as np

N=int(input())
A=list(map(int,input().split()))
Adic={}
for i in A:
  if Adic.get(i)==None:
    Adic[i]=1
  else:
    Adic[i]+=1
Q=int(input())
ope=[]

for i in range(Q):
  ope.append(list(map(int,input().split())))

A=np.array(A)

sum=0
for key,value in Adic.items():
  sum+=key*value
for b,c in ope:
  if Adic.get(b)!=None:
    if Adic.get(c)==None:Adic[c]=0
    sum=sum-b*Adic[b]+c*Adic[b]
    Adic[c]+=Adic.pop(b)
    print(sum)
  else:
    print(sum)
### BUGGY CODE ###

import sys
N = int(input())
A = map(int, input().split())
m = 1

for item in A:
    m *= item

if m > 10 ** 18:
    print("-1")
    sys.exit()
print(m)

### FIXED CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
m = 1
if 0 in A:
    print(0)
    sys.exit()

for item in A:
    m *= item
    if m > 10 ** 18:
        print("-1")
        sys.exit()
print(m)
### BUGGY CODE ###

import sys

def main():
    n=int(input())
    l=[int(e) for e in list(sys.stdin.readline().split())]
    i=1
    if i not in l:
        print(-1)
        return
    count=0
    while i in l:
        idx_i=l.index(i)
        count+=idx_i
        l=l[idx_i+1:]
        i+=1

    print(count+len(l))

main()

### FIXED CODE ###

import sys
si = sys.stdin.readline
so = sys.stdout.write


def main():
    n = int(si())
    l = [int(e) for e in si().split()]

    bn = 1
    count = 0
    for i in range(n):
        if l[i] == bn:
            bn += 1
        else:
            count += 1

    print(count if count != n else -1)


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

import sys
input = sys.stdin.readline
N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = 10 **18 +1
ok = inf
ng = -inf

def is_ok(arg):
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    return K > ans

while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
        ng = mid
    else:
        ok = mid
print(ng)


### FIXED CODE ###

N ,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
inf = max(A[0]**2,A[-1]**2)
ok1 = inf
ng1 = -inf
while (abs(ok1 - ng1) > 1):
    arg = (ok1 + ng1) // 2
    ans = 0
    for i in range(N):
        if A[i] * A[i] < arg :
            ans -= 1
        ok = N
        ng = -1
        if A[i] == 0:
            if arg > 0:
                ans += N
        elif A[i] > 0:
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ng = mid
                else:
                    ok = mid
            ans += ok
        else: 
            while (abs(ok - ng) > 1):
                mid = (ok + ng) // 2
                if A[i] * A[mid] < arg:
                    ok = mid
                else:
                    ng = mid       
            ans += N-ok   
    ans /= 2
    if K>ans:
        ng1 = arg
    else:
        ok1 = arg
print(ng1)
### BUGGY CODE ###

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

mod = 998244353
fact = [1] + [0] * n
inv_fact = [0] * (n+1)
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod

for i in range(n+1):
    inv_fact[i] = pow(fact[i],mod-2,mod)
    
def cb(n, k, mod):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % mod

ans = 0
for x in range(n+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        if y >= 0:
            if x > n or y > n:
                pass
            else:
                ans += cb(n, x, mod) * cb(n, y, mod)
                ans %= mod
    
print(ans)

### FIXED CODE ###

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

mod = 998244353
fact = [1] + [0] * n
inv_fact = [0] * (n+1)
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod

for i in range(n+1):
    inv_fact[i] = pow(fact[i],mod-2,mod)
    
def cb(n, k, mod):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % mod

ans = 0
for x in range(n+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        if y >= 0:
            if x > n or y > n:
                pass
            else:
                ans += cb(n, x, mod) * cb(n, y, mod)
                ans %= mod
    
print(ans)
### BUGGY CODE ###

import itertools


def main():
    n = int(input())
    a = map(int, input().split())
    count = 0
    for i in itertools.combinations(a, 2):
        count += i[0]*i[1]
    return count % (10**9+7)


if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import itertools


def main():
    count = 0
    MOD = 10**9+7
    n = int(input())
    a = list(map(int, input().split()))
    s = [0]
    for i in range(n-1):
        s.append((s[i]+a[i]) % MOD)
    for ai, si in zip(a, s):
        count += (ai*si) % MOD
    return count % MOD


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

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
px = [ list(map(int,input().split())) for _ in range(q) ]
# print(tree)
# print(px)
c = [0]*n
for i in range(len(px)):
    c[px[i][0]-1] += px[i][1]
# print(c)
# for i in range(1,n):
#     c[i] += c[min(tree[i])-1]
visited = [0]*n
visited[0] = 1
while sum(visited)!=n:
    for i in range(1,n):
        if visited[i]==0:
            for j in range(len(tree[i])):
                node_tmp = tree[i][j]
                if visited[node_tmp-1]==1:
                    c[i] += c[node_tmp-1]
                    visited[i] = 1
print(" ".join(map(str,c)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,q = map(int, input().split())
tree = [[] for _ in range(n)]
for _ in range(n-1):
    a,b = map(int, input().split())
    tree[a-1].append(b)
    tree[b-1].append(a)
# px = [ list(map(int,input().split())) for _ in range(q) ]
c = [0]*n
# for i in range(len(px)):
for _ in range(q):
    p,x = map(int,input().split())
    c[p-1] += x  
visited = [0]*n
cnd = [1]   # current_node
while len(cnd)>0:
    nnd = []
    for j in cnd:
        visited[j-1]=1
        ko = tree[j-1]
        for k in ko:
            if visited[k-1]==0:
                c[k-1] += c[j-1]
                nnd.append(k)
    cnd = nnd
print(" ".join(map(str,c)))
### BUGGY CODE ###

class RollingHash:
    def __init__(self, s, base, MOD):
        self.s = s
        self.l = l = len(s)
        self.base = base
        self.MOD = MOD
        self.h = h = [0]*(l + 1)
        for i in range(l):
            h[i+1] = (h[i] * base + ord(s[i])) % MOD
    def get(self, l, r):
        MOD = self.MOD
        return ((self.h[r] - self.h[l]*pow(self.base, r-l, MOD) + MOD)) % MOD

C = open(0).read().split()
MOD = 563980774085007485
for t in range(len(C)//2):
    S = C[2*t]; T = C[2*t+1]
    rhs = RollingHash(S, 31, MOD)
    rht = RollingHash(T, 31, MOD)
    L = len(S)
    hs = [set() for i in range(L+1)]
    for l in range(1, L+1):
        hsl = hs[l]
        for i in range(L-l+1):
            hsl.add(rhs.get(i, i+l))
    ans = 0
    M = len(T)
    for l in range(L, 0, -1):
        hsl = hs[l]
        for i in range(M-l+1):
            if rht.get(i, i+l) in hsl:
                break
        else:
            continue
        ans = l
        break
    print(ans)


### FIXED CODE ###

def rolling_hash(S, base, MOD):
    l = len(S)
    h = [0]*(l + 1)
    for i in range(l):
        h[i+1] = (h[i] * base + ord(S[i])) % MOD
    return h


C = open(0).read().split()
MOD = 358976445361682909
base = 31
for t in range(len(C)//2):
    S = C[2*t]; T = C[2*t+1]
    rhs = rolling_hash(S, base, MOD)
    rht = rolling_hash(T, base, MOD)
    L = len(S); M = len(T)
    def solve(l):
        v = pow(base, l, MOD)
        hs = set()
        for i in range(L-l+1):
            hs.add((rhs[i+l] - rhs[i]*v) % MOD)
        for i in range(M-l+1):
            if (rht[i+l] - rht[i]*v) % MOD in hs:
                return 1
        return 0
    left = 0; right = min(L, M)+1
    while left+1 < right:
        mid = (left + right) // 2
        if solve(mid):
            left = mid
        else:
            right = mid
    print(left)
### BUGGY CODE ###

def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N = I()
    S = SI()
    Q = I()
    K = LI()
    ans = []
    for k in K:
        D = 0; M = 0; C = 0
        now = 0
        for i, s in enumerate(S):
            if s == "D":
                D += 1
            if s == "M":
                M += 1
                now += D
            if s == "C":
                C += now
            if i>=k-1:
                if S[i-k+1] == "D":
                    D -= 1
                    now -= M
                if S[i-k+1] == "M":
                    M -= 1
#        print(D, M, C)
        ans.append(C)
    for v in ans:
        print(v)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

### FIXED CODE ###

def examA():
    N = I()
    ans = 0
    print(ans)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    N = I()
    S = SI()
    Q = I()
    K = LI()
    ans = []
    for k in K:
        D = 0; M = 0; C = 0
        now = 0
        for i in range(N):
            s = S[i]
            if s == "D":
                D += 1
            elif s == "M":
                M += 1
                now += D
            elif s == "C":
                C += now
            if i>=k-1:
                if S[i-k+1] == "D":
                    D -= 1
                    now -= M
                elif S[i-k+1] == "M":
                    M -= 1
#        print(D, M, C)
#        ans.append(C)
        print(C)
#    for v in ans:
#        print(v)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""
### BUGGY CODE ###

H = int(input())

lst = [0]
for i in range(1, 10**12):
    if i == 1:
        lst.append(1)
    else:
        tmp = lst[i//2]*2 + 1
        lst.append( tmp )
    
    if i == H:
        print(lst[i])
        exit()

### FIXED CODE ###

H = int(input())

ans = 1

if H == 1:
    print(1)
    exit()

while True:
    tmp = ans*2 + 1
    if H > ans and H <= tmp:
        print(tmp)
        exit()
    else:
        ans = tmp