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

n=int(input())
ans=1
for i in range(n):
  ans*=i+1
print(int(ans%(10**9+7)))

### FIXED CODE ###

n=int(input())
ans=1
for i in range(n):
  ans*=i+1
  ans%=10**9+7
print(ans)
### BUGGY CODE ###

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

exarr = [(i+1)/2 for i in arr]
sol = 0

for i in range(n-k+1):
    tmpsum = sum(exarr[i:i+k])
    sol = max(sol,tmpsum)
    
print(sol)

### FIXED CODE ###

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

exarr = [(i+1)/2 for i in arr]
tmpsum = sum(exarr[:k])
sol = tmpsum

for i in range(n-k):
    tmpsum = tmpsum - exarr[i] + exarr[i+k]
    sol = max(sol,tmpsum)
    
print(sol)
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
S = input()
ans = 0
ws = defaultdict(list)
for l in range(1, N // 2 + 1):
    for i in range(0, N - l + 1):
        w = S[i:i+l]
        if len(ws[w]) > 0:
            if ws[w][-1] < i:
                ws[w].append(i)
        else:
            ws[w].append(i)
for k, v in ws.items():
    if len(v) <= 1:
        continue
    else:
        ans = max(ans, len(k))
print(ans)
        

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
S = input()
dp = [[0] * 5005 for _ in range(5005)]

for i in range(N - 1, -1, -1):
    for j in range(N - 1, -1, -1):
        if S[i] == S[j]:
            dp[i][j] = dp[i + 1][j + 1] + 1
ans = 0
for i in range(N):
    for j in range(N):
        if i >= j:
            continue
        now = min(dp[i][j], j - i)
        ans = max(now, ans)
print(ans)
### BUGGY CODE ###

import sys

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

ans = 1

for a in A:
    ans *= a

if 10**18 < ans:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys

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

ans = 1

for a in A:
    if a == 0:
        print(0)
        sys.exit()

for a in sorted(A, reverse=True):
    ans *= a
    if 10**18 < ans:
        print(-1)
        sys.exit()


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

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

cumul = 1
for i in range(N):
    cumul *= nums[i]

if cumul > 10 ** 18: print(-1)
else: print(cumul)


### FIXED CODE ###

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

cumul = 1
if 0 in nums:
    print(0)
else:
    for i in range(N):
        cumul *= nums[i]
        if cumul > 10 ** 18:
            print(-1)
            break
    if cumul <= 10 ** 18: print(cumul)
### BUGGY CODE ###

import math
print math.factorial(int(raw_input()))%(10**9+7)

### FIXED CODE ###

mod=10**9+7
ans=1
for i in xrange(int(raw_input())):
    ans*=i+1
    ans%=mod
print ans
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
s = input()
c = 0
f = defaultdict(list)
for i in range(n):
	f[s[i]].append(i)
for i in range(n):
	for j in range(i+1, n):
		if  s[i] != s[j]:
			for k in f:
				if k != s[i] and k != s[j]:
					for m in f[k]:
						if m > j and 2*j - i != m:
							c += 1
print(c)

### FIXED CODE ###

n = int(input())
s = input()
# B_map = set()
R, G, B = 0, 0, 0
for i in range(n):
	if s[i] == 'R':
		R += 1
	elif s[i] == 'G':
		G += 1
	else:
		B += 1

res = R * G * B

for i in range(n):
	for j in range(i+1, n):
		temp = 2*j - i
		if temp < n and s[i] != s[j] and s[j] != s[temp] and s[temp] != s[i]:
			res -= 1
print(res)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])

def dfs(h, w):
    cnt = 0
    if grid[h][w] == "#":
        return cnt
    q = deque([(h, w, "No")])
    cnt += 1
    while q:
        h, w, direct = q.pop()
        for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            if 0 <= h + i < H and 0 <= w + j < W and grid[h + i][w + j] == ".":
                if direct == "No" or direct == (i, j):
                    cnt += 1
                    q.append((h + i, w + j, (i, j)))
            else:
                continue
    return cnt 
    
ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans, dfs(h, w))
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
grid = []
for _ in range(H):
    grid.append([s for s in input()])
    
left = [[0 for _ in range(W)] for _ in range(H)]
right = [[0 for _ in range(W)] for _ in range(H)]
up = [[0 for _ in range(W)] for _ in range(H)]
down = [[0 for _ in range(W)] for _ in range(H)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == ".":
            if w == 0:
                left[h][w] = 1
            else:
                left[h][w] += left[h][w - 1] + 1

for h in range(H):
    for w in range(W)[::-1]:
        if grid[h][w] == ".":
            if w == W - 1:
                right[h][w] = 1
            else:
                right[h][w] += right[h][w + 1] + 1
            
for w in range(W):
    for h in range(H):
        if grid[h][w] == ".":
            if h == 0:
                up[h][w] = 1
            else:
                up[h][w] += up[h - 1][w] + 1
                
for w in range(W):
    for h in range(H)[::-1]:
        if grid[h][w] == ".":
            if h == H - 1:
                down[h][w] = 1
            else:
                down[h][w] += down[h + 1][w] + 1
                
ans = -10000
for h in range(H):
    for w in range(W):
        ans = max(ans, up[h][w] + down[h][w] + right[h][w] + left[h][w] - 3)
print(ans)
### BUGGY CODE ###

n,a,b = map(int,input().split())
mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(2*(10**5)+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
fact2 = 1
for i in range(n,n-a,-1):
    fact2 = fact2 * i %mod
fact3 = fact2
for i in range(n-a,n-b,-1):
    fact3 = fact3 * i %mod
def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
#print(fact2,fact3,fact_inv[a],fact_inv[b])
ans = (2 ** n - 1) % mod
ans -= fact2 * fact_inv[a] % mod
ans -= fact3 * fact_inv[b] % mod
if ans < 0:
    ans += mod
print(ans)

### FIXED CODE ###

n,a,b = map(int,input().split())
mod = 10 ** 9 + 7
fact = [1]
fact_inv = [1]
for i in range(2*(10**5)+5):
    new_fact = fact[-1]*(i+1)%mod
    fact.append(new_fact)
    fact_inv.append(pow(new_fact,mod-2,mod))
fact2 = 1
for i in range(n,n-a,-1):
    fact2 = fact2 * i %mod
fact3 = fact2
for i in range(n-a,n-b,-1):
    fact3 = fact3 * i %mod
#print(fact2,fact3,fact_inv[a],fact_inv[b])
ans = (2 ** n - 1) % mod
ans -= fact2 * fact_inv[a] % mod
if ans < 0:
    ans += mod
ans -= fact3 * fact_inv[b] % mod
if ans < 0:
    ans += mod
print(ans)
### BUGGY CODE ###

n,d=map(int,input().split())
print(sum(eval("(("+input().replace(" ",")**2+(")+")**2)**0.5<=d") for _ in range(n)))

### FIXED CODE ###

n,d=map(int,input().split())
print(sum(eval("(("+input().replace(" ",")**2+(")+")**2)")**0.5<=d for _ in range(n)))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
a = LIST()
count = 0
flag = 0

while flag == 0:
	# print(a)
	for i in range(N):
		if a[i] % 2 == 0:
			a[i] = int(a[i]/2)
			count += 1
			break
	else:
		flag = 1
print(count)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
a = LIST()
count = 0
flag = 0
"""
while flag == 0:
	print(a)
	for i in range(N):
		if a[i] % 2 == 0:
			a[i] = int(a[i]/2)
			count += 1
			break
	else:
		flag = 1
"""
for i in a:
    while i % 2 == 0:
        count += 1
        i /= 2
print(count)
### BUGGY CODE ###

n = int(input()) // 2
ns = list(map(int, input().split()))
a = [ns[i] for i in range(len(ns)) if i % 2 == 0]
b = [ns[i] for i in range(len(ns)) if i % 2 == 1]
sa = set(a)
sb = set(b)
ca = sorted([(a.count(s), s) for s in sa])[::-1]
cb = sorted([(b.count(s), s) for s in sb])[::-1]  # [(出た回数, num)]
if ca[0][1] != cb[0][1]:
    print(n-ca[0][0] + n-cb[0][0])
else:
    if len(ca) == 1 and len(cb) == 1:
        print(n)
    elif len(ca) == 1:
        print(n-ca[0][0] + n-cb[1][0])
    else:
        print(n-ca[1][0] + n-cb[0][0])

### FIXED CODE ###

n = int(input()) // 2
ns = list(map(int, input().split()))

a = [ns[i] for i in range(len(ns)) if i % 2 == 0]
b = [ns[i] for i in range(len(ns)) if i % 2 == 1]
#ca = sorted([(a.count(s), s) for s in sa])[::-1]
#cb = sorted([(b.count(s), s) for s in sb])[::-1]  # [(出た回数, num)]
# countが遅かったので
da = {}
db = {}
for s in a:
    da[s] = da.get(s, 0) + 1
for s in b:
    db[s] = db.get(s, 0) + 1
ca = sorted([(v, k) for k, v in da.items()])[::-1]
cb = sorted([(v, k) for k, v in db.items()])[::-1]

if ca[0][1] != cb[0][1]:
    print(n-ca[0][0] + n-cb[0][0])
else:
    if len(ca) == 1 and len(cb) == 1:
        print(n)
    elif len(ca) == 1 and len(cb) > 1:
        print(n-ca[0][0] + n-cb[1][0])
    elif len(ca) > 1 and len(cb) == 1:
        print(n-ca[1][0] + n-cb[0][0])
    else:
        print(min(n-ca[1][0] + n-cb[0][0], n-ca[0][0] + n-cb[1][0]))  # ?
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import re

n = int(raw_input())
a = re.split('\s', raw_input())

first = ""
second = ""

if (n % 2 == 0):
        for i in range(n):
                if (i % 2 == 0):
                        if (second == ""):
                                second = a[i]
                        else:   
                                second = second + " " + a[i]
                else:   
                        if (first == ""):
                                first = a[i]
                        else:   
                                first = a[i] + " " + first
else:   
        for i in range(n):
                if (i % 2 == 1):
                        if (second == ""):
                                second = a[i]
                        else:   
                                second = second + " " + a[i]
                else:   
                        if (first == ""):
                                first = a[i]
                        else:   
                                first = a[i] + " " + first

print first + " " + second


### FIXED CODE ###

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

import re

n = int(raw_input())
a = re.split('\s', raw_input())

ans = [0]*n

if (n % 2 == 0):
        first = n / 2 - 1
        second = n / 2
        for i in range(n):
                if (i % 2 == 0):
                        ans[second] = a[i]
                        second += 1
                else:   
                        ans[first] = a[i]
                        first -= 1
else:   
        first = (n - 1) / 2
        second = (n - 1) / 2 + 1
        for i in range(n):
                if (i % 2 == 1):
                        ans[second] = a[i]
                        second += 1
                else:   
                        ans[first] = a[i]
                        first -= 1
ans = map(str, ans)
print " ".join(ans)
### BUGGY CODE ###

S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
result = 0
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  result += counter[mods[-1]] - 1
  d *= 10

print(result)

### FIXED CODE ###

S = input()
S = S[::-1]
d = 1
mods = [0]
counter = [0]*2019
counter[0] += 1
result = 0
for s in S:
  s = int(s)
  mods.append((mods[-1]+s*d)%2019)
  counter[mods[-1]] += 1
  result += counter[mods[-1]] - 1
  d *= 10
  d %= 2019

print(result)
### BUGGY CODE ###

def slv(n,a,s):
    dp=[set(()) for _ in '_'*(n+1)]
    dp[-1]={0}
    for i in range(n-1,-1,-1):
        if s[i]=='0':
            for j in dp[i+1]:
                dp[i].add(a[i]^j)
                dp[i].add(j)
        else:
            if a[i] in dp[i+1]:
                dp[i]=dp[i+1]
            else:
                dp[i]=set(())
            """
            for j in dp[i+1]:
                if a[i]^j in dp[i+1]:
                    dp[i].add(j)
                    dp[i].add(j^a[i])
            """
        if not dp[i]:return 1
    if dp[0]:return 0
    return 1

t=int(input())
n=[]
a=[]
s=[]
for _ in range(t):
    n.append(int(input()))
    a.append(list(map(int,input().split())))
    s.append(input())
for i in range(t):
    print(slv(n[i],a[i],s[i]))

"""
3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000

1
0
0
"""

### FIXED CODE ###

def slv(n,a,s):
  base=[0]
  for i in range(n-1,-1,-1):
    v=a[i]
    for j in sorted(base,reverse=True):
      v=min(v,j^v)
    if v==0:
      pass
    else:
      if s[i]=='0':base.append(v)
      if s[i]=='1':return 1
  if base:return 0
  return 1

t=int(input())
n=[]
a=[]
s=[]
for _ in range(t):
  n.append(int(input()))
  a.append(list(map(int,input().split())))
  s.append(input())
for i in range(t):
  print(slv(n[i],a[i],s[i]))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
    a = A.copy()
    del a[i]
    print(max(a))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
a = sorted(A.copy())
a1 = a[len(A)-1]
a2 = a[len(A)-2]

for i in A:
    if i == a1:
        print(a2)
    else:
        print(a1)
### BUGGY CODE ###

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

E = []
for p in P:
  E.append((p+1)*p/2/p)
mx = 0
for i in range(N-K+1):
  mx = max(sum(E[i:i+K]),mx)
print(mx)


### FIXED CODE ###

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

E = []
for p in P:
  E.append((p+1)*p/2/p)
csum = [0]
for i in range(N):
  csum.append(csum[-1]+E[i])
mx = 0
for i in range(N-K+1):
  mx = max(csum[K+i]-csum[i],mx)
print(mx)
### BUGGY CODE ###

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

sums=1
for i in A:
    sums=sums*i
if sums>1000000000000000000:
    print(-1)
else:
    print(sums)

### FIXED CODE ###

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

sums=1
for i in A:
    sums=sums*i
    if sums>1000000000000000000:
        sums=-1
        break
    
if 0 in A:
    print(0)
else:
    print(sums)
### BUGGY CODE ###

def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [float("inf") for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min([dp[i-a] + b for a, b in magic if i-a >= 0], default=dp[i])

    ans = min(dp[H:H+max_a])
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    H, N = [int(x) for x in input().split()]
    magic = [list(map(int, input().split())) for _ in range(N)]
    # print(magic)
    max_a = max(a for a, _ in magic)
    dp = [10**18 for _ in range(H + max_a)]
    dp[0] = 0

    for i in range(1, H+max_a):
        dp[i] = min(dp[i-a] + b for a, b in magic)

    ans = min(dp[H:H+max_a])
    print(ans)


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

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    

dots = XY[:]

import sys
INT_MAX = sys.maxsize

x_dots = [(x, y) for x, y in dots]
x_dots = sorted(x_dots)
y_dots = [(x, y) for x, y in dots]
y_dots = sorted(y_dots, key=lambda x: x[1])

ans = INT_MAX
for l in range(N):
    for r in range(l+1, N+1):
        for u in range(N):
            for t in range(u+1, N+1):
                xy_dots =  set(x_dots[l:r]) & set(y_dots[u:t])
                if len(xy_dots) >= K:
                    #print("---")
                    #print(l, r, x_dots[l:r])
                    #print(u, t, y_dots[u:t])
                    #print(x_dots[l:r])
                    l_val = x_dots[l:r][0][0]
                    r_val = x_dots[l:r][-1][0]
                    
                    u_val = y_dots[u:t][0][1]
                    t_val = y_dots[u:t][-1][1]
                    #print((r-l)*(t-u))
                    if ans > (r_val-l_val)*(t_val-u_val):
                        ans = (r_val-l_val)*(t_val-u_val)
print(ans)


#y_dots = sorted(y_dots, key=lambda x: x[1])
#ans = INT_MAX


### FIXED CODE ###

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

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
dots = XY[:]

import sys
INT_MAX = sys.maxsize

ans = INT_MAX

import itertools
for ((left_x, _), (right_x, _)) in itertools.combinations(dots, 2):
    if left_x > right_x:
        left_x, right_x = right_x, left_x
    for ((_, under_y), (_, top_y)) in itertools.combinations(dots, 2):
        if under_y > top_y:
            under_y, top_y = top_y, under_y
        counter = 0
        for d_x, d_y in dots:
            if  (left_x <= d_x) and (d_x <= right_x) and (under_y <= d_y) and (d_y <= top_y):
                counter += 1
                
        if counter >= K:
            area = (top_y-under_y) * (right_x-left_x)
            if ans > area:
                ans = area
            
print(ans)
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque

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

    edge = defaultdict(list)

    for _ in range(M):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    first = 1
    second = edge[1][0]

    visited = [False] * (N + 1)
    visited[first] = True
    visited[second] = True

    def dfs(u):
        path = [u]
        for v in edge[u]:
            if not visited[v]:
                visited[v] = True
                path.extend(dfs(v))
                break
        return path

    res1 = dfs(first)
    res2 = dfs(second)

    print(len(res1) + len(res2))
    print(*res1[::-1], *res2)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict, deque

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

    edge = defaultdict(list)

    for _ in range(M):
        a, b = map(int, readline().split())
        edge[a].append(b)
        edge[b].append(a)

    first = 1
    second = edge[1][0]

    visited = [False] * (N + 1)
    visited[first] = True
    visited[second] = True

    que = deque()
    que.append(first)

    path1 = []
    path2 = []

    flag = True

    while flag:
        u = que.popleft()
        path1.append(u)
        flag = False
        for v in edge[u]:
            if not visited[v]:
                visited[v] = True
                que.append(v)
                flag = True
                break

    que = deque()
    que.append(second)
    flag = True

    while flag:
        u = que.popleft()
        path2.append(u)
        flag = False
        for v in edge[u]:
            if not visited[v]:
                visited[v] = True
                que.append(v)
                flag = True
                break

    print(len(path1) + len(path2))
    print(*path1[::-1], *path2)


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

N = int(input())
n = str(N)
a = list(n)

count = 0

for i in range(len(a)):
  count = count + int(a[i]) % (10**(i+1))

if count % 9 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N = int(input())
n = str(N)
a = list(n)

count = 0

for i in range(len(a)):
  count = count + int(a[i])

if count % 9 == 0:
  print("Yes")
else:
  print("No")
### BUGGY CODE ###

import itertools
while 1:
    n,m,s=map(int,input().split())
    if n==0:break
    dp=[[0 for _ in range(s+2)] for _ in range(n*n+1)]
    dp[0][0]=1
    for i,j in itertools.product(range(1,m+1),range(n*n,0,-1)):
        for k in range(i,s+1):
            dp[j][k]=(dp[j][k]+dp[j-1][k-i])%100000
    print(dp[n*n][s])

### FIXED CODE ###

import itertools
while 1:
    n,m,s=map(int,input().split())
    if n==0:break
    dp=[[0 for _ in range(s+1)] for _ in range(n*n+1)]
    dp[0][0]=1
    for i,j in itertools.product(range(1,n*n+1),range(s+1)):
        if j>=i:dp[i][j]+=dp[i-1][j-i]+dp[i][j-i]
        if j-m>=1:dp[i][j]-=dp[i-1][j-m-1]
        dp[i][j]%=100000
    print(dp[n*n][s])
### BUGGY CODE ###

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

def f(l, mn):
    ng = -1
    ok = len(l)
    while abs(ng - ok) > 1:
        i = (ok + ng) // 2
        x = l[i]
        if mn < x:
            ok = i
        else:
            ng = i
    return ok

ans = 0
for a in A:
    for bi in range(f(B, a), N):
        b = B[bi]
        ans += N - f(C, b)
print(ans)

### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort()
C.sort()

ans = 0
for b in B:
    acnt = bisect_left(A, b)
    ccnt = N - bisect_right(C, b)
    ans += acnt * ccnt
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())), reverse=True)
C = []
for _ in range(M):
  b, c = map(int,input().split())
  C.extend([c]*b)
C.sort(reverse=True)
lenC = len(C)
ans = -float('inf')
for i in range(N+1):
  if i == 0:
    if lenC >= N:
      tmp_ans = sum(C[:N])
      idxC = N-1
      idxA = 0
    else:
      tmp_ans = sum(C) + sum(A[:N-lenC])
      idxC = lenC - 1
      idxA = N-lenC
  else:
    #print(lenC, N, idxC, idxA)
    tmp_ans = tmp_ans - C[idxC] + A[idxA]
    idxC -= 1
    idxA += 1
  ans = max(ans,tmp_ans)
  if idxC < 0 or idxA > N: break

print(ans)

### FIXED CODE ###

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

CB = []
for _ in range(M):
  b,c = map(int,input().split())
  CB.append([c,b])
CB.sort(reverse=True)

num = 0
ans = 0 
for c,b in CB:
  for bi in range(b):
    if num >= N: break
    if num > N or c<=A[num]:
      break
    else:
      num += 1
      ans += c
print(ans+sum(A[num:]) if num != N else ans)
### BUGGY CODE ###

#D問題
import math
N,M = map(int,input().split())
A = list(map(int,input().split()))

A.sort(reverse=True)
for j in range(M):
    A[0] = A[0]//2
    A.sort(reverse=True)
    
print(sum(A))

### FIXED CODE ###

#D問題
import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))

B = []
for a in A:
    heapq.heappush(B,-a)

for j in range(M):
    b = -heapq.heappop(B)
    b = b//2
    heapq.heappush(B,-b)
    
print(-sum(B))
### BUGGY CODE ###

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

for (l, r) in data:
	print(S[l-1:r].count("AC"))



### FIXED CODE ###

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

t = [0] * (N + 1) 

for i in range(N):
	t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)

for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])