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

from collections import Counter

n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
p, q, r = cnt[1], cnt[2], cnt[3]

dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]

for k in range(r + 1):
    for j in range(r + q + 1):
        for i in range(n + 1):
            if not (0 < i + j + k <= n):
                continue
            if i > 0:
                dp[i][j][k] += dp[i - 1][j][k] * i
            if j > 0:
                dp[i][j][k] += dp[i + 1][j - 1][k] * j
            if k > 0:
                dp[i][j][k] += dp[i][j + 1][k - 1] * k
            dp[i][j][k] += n
            dp[i][j][k] /= (i + j + k)

print(dp[p][q][r])


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = [0,0,0]
for x in LI():
    a[x-1] += 1
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(a[2]+1):
    for j in range(a[1]+a[2]+1):
        for i in range(N+1):
            if not (0 < i+j+k <= N): continue
            x = 0.0
            if i > 0: x += dp[i-1][j][k] * (i/N)
            if j > 0: x += dp[i+1][j-1][k] * (j/N)
            if k > 0: x += dp[i][j+1][k-1] * (k/N)
            x += 1.0
            x *= N / (i+j+k)
            dp[i][j][k] = x
print(dp[a[0]][a[1]][a[2]])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
 
def gcd(a,b):
    a,b = max(a,b),min(a,b)
    while a%b!=0:
        a,b = b,a%b
    return b

mod = 10**9 + 7

l = A[0]
for i in range(1,N):
    l = A[i]*l//gcd(A[i],l)


ans = 0
for i in range(N):
    ans+=l//A[i]
    ans%=mod
    
print(ans)

### FIXED CODE ###


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

mod = 10**9 + 7

from collections import defaultdict

B = [defaultdict(int) for i in range(N)]
C = defaultdict(int)

for x in range(N):
    a = A[x]
    for i in range(2,int(a**0.5)+1):
        while a%i==0 and a>0:
            B[x][i]+=1
            a//=i
            #print(a)
            C[i]=max(C[i],B[x][i])
    #print(a)
    if a>1:
        B[x][a]+=1
        C[a] = max(C[a],B[x][a])
#print(B,C)
l = 1
for key in C:
    l*=pow(key,C[key],mod)
    l%=mod

ans = 0
for i in range(N):
    b = l
    for key in B[i]:
        c = pow(key,B[i][key],mod)
        b *= pow(c,mod-2,mod)
    ans+=b
    ans%=mod

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

import collections
n = int(raw_input())
h = collections.Counter()
for x in range(1,n+1):
	for y in range(1,n+1):
		for z in range(1,n+1):
			q = x ** 2 + y ** 2 + z ** 2
			q += x*y + y*z + z * x
			if q > n:
				break
			h[q] +=1 
for i in range(1,n+1):
	print h[i]

### FIXED CODE ###

import collections
n = int(raw_input())
h = collections.Counter()
for x in range(1,n+1):
	if x ** 2 > n:
		break
	for y in range(1,n+1):
		if x ** 2 + y ** 2 + x * y > n:
			break
		for z in range(1,n+1):
			q = x ** 2 + y ** 2 + z ** 2
			q += x*y + y*z + z * x
			if q > n:
				break
			h[q] +=1 
for i in range(1,n+1):
	print h[i]
### BUGGY CODE ###

import copy
N,K=map(int,input().split())
L=[]
for i in range(N):
    a,b=map(int,input().split())
    if a<=K:
        L.append([a,b])

#print(L)
k=[]
num=copy.deepcopy(K)
for i in range(30):
    if num//(2**(29-i))==1:
        k.append(1)
        num%=(2**(29-i))
    else:
        k.append(0)
        num%=(2**(29-i))
        
ans=0
for a,b in L:
    f=0
    for i in range(30):
        if a//(2**(29-i))==1 and k[i]==0:
            f=1
            break
        else:
            a%=(2**(29-i))
    if f==0:
        ans+=b
NUM=0

for i in range(29):
    if k[i]==1:
        cnt=0
        NUM+=2**(29-i)
        for a,b in L:
            if a<NUM:
                A=copy.deepcopy(a)
                A%=(2**(30-i))
                if A//(2**(29-i))==0:
                    cnt+=b
        if ans<cnt:
            ans=cnt
        #print(cnt,NUM)
    else:
        l=[]
        for a,b in L:
            A=copy.deepcopy(a)
            A%=2**(30-i)
            if A//(2**(29-i))==0:
                l.append([a,b])
        L=l
print(ans)
#print(k)

### FIXED CODE ###

import copy
N,K=map(int,input().split())
L=[]
for i in range(N):
    a,b=map(int,input().split())
    if a<=K:
        L.append([a,b])

#print(L)
k=[]
num=copy.deepcopy(K)
for i in range(30):
    if num//(2**(29-i))==1:
        k.append(1)
        num%=(2**(29-i))
    else:
        k.append(0)
        num%=(2**(29-i))
        
ans=0
for a,b in L:
    if K|a==K:
        ans+=b
NUM=0
for i in range(30):
    if k[i]==1:
        cnt=0
        NUM+=2**(29-i)
        for a,b in L:
            if K-2**(29-i)|a<NUM:
                cnt+=b
        if ans<cnt:
            ans=cnt
        #print(cnt,i,K-2**(29-i))
    
print(ans)
#print(k)
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = [LI() for _ in range(n)]
xy.sort(key = itemgetter(1),reverse = True)
ans = inf
for i in range(n):
    ux,uy = xy[i]
    for j in range(i+1,n):
        dx,dy = xy[j]
        for k in range(n):
            rx,ry = xy[k]
            for l in range(n):
                lx,ly = xy[l]
                if rx < lx:
                    continue
                cnt = 0
                for m in range(n):
                    x,y = xy[m]
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
#ABC75 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n,K = LI()
xy = []
X = []
Y = []
for _ in range(n):
    x,y = LI()
    xy.append([x,y])
    X.append(x)
    Y.append(y)
X.sort(reverse = True)
Y.sort(reverse = True)
ans = inf
for i in range(n):
    uy = Y[i]
    for j in range(i+1,n):
        dy = Y[j]
        for k in range(n):
            rx = X[k]
            for l in range(k+1,n):
                lx = X[l]
                cnt = 0
                for x,y in xy:
                    if lx <= x <= rx and dy <= y <= uy:
                        cnt += 1
                if cnt >= K:
                    S = (uy - dy)*(rx - lx)
                    ans = min(ans,S)
print(ans)
### BUGGY CODE ###

import bisect
import heapq
N,Q = list(map(int,input().split(" ")))

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q


for i in range(N):
    S,T,X =list(map(int,input().split(" ")))
    lt = S -X -0.5
    rt = T -X -0.5
    queries.append([lt,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])



for i in range(Q):
    t = int(input())
    hitos.append(t)
for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l)
     rind  = bisect.bisect_left(hitos,r)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)


### FIXED CODE ###

import bisect
import heapq
import sys
N,Q = [int(x) for x in sys.stdin.readline().split()]

hitos = []
ans = [-1] * Q
queries =[]
jump = [-1] * Q



queries = [[int(x) for x in sys.stdin.readline().split()] for i in range(N)]
hitos = [int(sys.stdin.readline()) for i in range(Q)]


# for i in range(N):
    # S,T,X =list(map(int,input().split(" ")))
    # lt = S -X -0.5
    # rt = T -X -0.5
    # queries.append([lt,rt,X]) #-1 → 挿入クエリ lが時間、-1がクエリの種類、Xが場所


queries.sort(key=lambda x:x[2])





for l,r,x in queries:
     lind  = bisect.bisect_left(hitos,l-x - 0.5)
     rind  = bisect.bisect_left(hitos,r -x - 0.5)
     while lind < rind:
         if ans[lind] == -1:
            ans[lind] = x
            jump[lind] = rind
            lind += 1
         else:
             temp = jump[lind]
             jump[lind] = rind
             lind = temp

for i  in ans:
    print(i)
### BUGGY CODE ###

import sys
 
a = []
for l in sys.stdin:
    if l == '\n' or l == '\r' or l == '\r\n':
        break
    else :
        a.append(l)
 
target = a[int(a[0])]
num = 0
for i in range(1, len(a) - 1):
    for j in range(i + 1, len(a)):
        flag = False
        iStrSorted = ''.join(sorted(a[i]))
        jStrSorted = ''.join(sorted(a[j]))
        if iStrSorted==jStrSorted:
            flag = True
        else:
            flag = False
        if flag:
            num = num + 1
print(num)

### FIXED CODE ###

import sys
import collections

n=int(input())
a=[''.join(sorted(input())) for _ in range(n)]

ans = 0
for v in collections.Counter(a).values():
    if v != 1:
        ans += v * (v - 1) // 2
print(ans)
### BUGGY CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 200000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)

### FIXED CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 30000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)
### BUGGY CODE ###

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

l = 0
r = k
ansl = 0
ansr = 0
ans=0
for i in range(n - k + 1):
    tmp = sum(p[i:i + k])
    # print(i,i+k,tmp)
    if tmp > ans:
        ansl = i
        ansr = i + k - 1
        ans=tmp
# print(ansl, ansr)
ans2 = 0
for i in range(ansl, ansr + 1):
    ans2 += (p[i] + 1) / 2
print(ans2)


### FIXED CODE ###

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

ansl = 0
ansr = k-1
ans = 0
tmp = sum(p[:k])
# print(tmp)
for i in range(1,n - k+1):
    tmp = tmp - p[i-1] + p[i + k-1]
    # print(i,i+k-1,tmp)
    if tmp > ans:
        ansl = i
        ansr = i + k - 1
        ans = tmp
# print(ansl, ansr)
ans2 = 0
for i in range(ansl, ansr + 1):
    ans2 += (p[i] + 1) / 2
print(ans2)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
m = int(input())

def dfs(u, v):
  parent = [-1]*n
  seen = [False]*n
  stack = [u]
  seen[u] = True
  while stack:
    nv = stack[-1]
    if nv == v:
      return stack
    f = True
    for i in T[nv]:
      if seen[i]:
        continue
      stack.append(i)
      seen[i] = True
      f = False
      break
    if f:
      stack.pop()

E = [set() for _ in range(m)]
for i in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  edge = dfs(u, v)
  for j in range(len(edge)-1):
    E[i].add((min(edge[j], edge[j+1]), max(edge[j], edge[j+1])))

ans = 0
for i in range(2**m):
  s = set()
  for j in range(m):
    if i>>j & 1:
      s |= E[j]
  cnt = bin(i).count("1") % 2
  ans += (-1)**cnt * 2**(n-1-len(s))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
  n = int(input())
  T = [[] for _ in range(n)]
  D = {}
  for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
    D[(a, b)] = 1<<i
    D[(b, a)] = 1<<i
  m = int(input())

  def dfs(u, v):
    parent = [-1]*n
    seen = [False]*n
    stack = [u]
    seen[u] = True
    while stack:
      nv = stack[-1]
      if nv == v:
        return stack
      for i in T[nv]:
        if seen[i]:
          continue
        stack.append(i)
        seen[i] = True
        break
      else:
        stack.pop()

  E = [0]*m
  for i in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    edge = dfs(u, v)
    for j in range(len(edge)-1):
      E[i] |= D[(edge[j], edge[j+1])]

  ans = 0
  for i in range(2**m):
    s = 0
    for j in range(m):
      if i>>j & 1:
        s |= E[j]
    cnt = bin(i).count("1") % 2
    ans += (-1)**cnt * 2**(n-1-bin(s).count("1"))
  print(ans)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

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

answer = 1
if 0 in A:
  print(0)
else:
  for i in A:
    answer *= i
  if answer > 10**18:
    print(-1)
  else:
    print(answer)


### FIXED CODE ###

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

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

import math

def nCr(n,r):
    return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))


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

l = [2]
now = 3

while now ** 2 <= M:
    flag = True
    for i in l:
        if now % i == 0:
            flag = False
            break
    if flag:
        l.append(now)
    now += 2

dic = {}
for i in l:

    while M % i == 0:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1

        M //= i

if M != 1:
    dic[M] = 1

ans = 1
#print (dic)

for i in dic:
    ans *= nCr(dic[i] + N - 1,dic[i])
    #print (ans)
    ans %= (10 ** 9 + 7)
print (ans % (10**9+7))


### FIXED CODE ###

import sys
mod = 1000000007

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, pow(b, mod-2,mod))

ivl = [0]
def inverse_max(a): #下2つを使用する際の下準備

    now = 1
    for i in range(a):
        i += 1
        now *= i
        now %= mod
        ivl.append(now)

def nCr(n,r):
    return div(ivl[n] , mul(ivl[n-r] , ivl[r]))


N,M = map(int,input().split())
inverse_max(N + 40)

if N == 1:
    print (1)
    sys.exit()

l = [2]
now = 3

while now ** 2 <= M:
    flag = True
    for i in l:
        if now % i == 0:
            flag = False
            break
    if flag:
        l.append(now)
    now += 2

dic = {}
for i in l:

    while M % i == 0:
        if i not in dic:
            dic[i] = 1
        else:
            dic[i] += 1

        M //= i

if M != 1:
    dic[M] = 1

ans = 1
#print (dic)

for i in dic:
    ans *= nCr(dic[i] + N - 1,dic[i])
    #print (ans)
    ans %= (10 ** 9 + 7)
print (ans % (10**9+7))
### BUGGY CODE ###

#coding:utf-8


if __name__ == "__main__":
    N, M = map(int, input().split())
    city_list = []
    pref_dec = {}
    for m in range(M):
        p, y = map(int, input().split())
        city_list.append((p, y))
        if p not in pref_dec:
            pref_dec[p] = []
        pref_dec[p].append(y)

    for p in set(pref_dec.keys()):
        pref_dec[p].sort()

    for m in range(M):
        p_id = city_list[m][0]
        y_id = pref_dec[p_id].index(city_list[m][1]) + 1
        print(str(p_id).zfill(6) + str(y_id).zfill(6))


### FIXED CODE ###

#coding:utf-8
#参考：https://beta.atcoder.jp/contests/abc113/submissions/3806710


if __name__ == "__main__":
    N, M = map(int, input().split())
    city_list = []
    for i in range(M):
        p, y = map(int, input().split())
        city_list.append([i, p, y])

    city_count = {}
    order_dic = {}
    for i, p, y in sorted(city_list, key = lambda x: x[2]):
        if not p in city_count:
            city_count[p] = 0
        city_count[p] += 1
        order_dic[i, p] = city_count[p]

    for i, p, y in city_list:
        print("{:06}{:06}".format(p, order_dic[i,p]))
### BUGGY CODE ###

import itertools
n, x, y = map(int, input().split())
x -= 1
y -= 1
list1 = [[0 for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        num = min([abs(j - i), abs(x - i) + 1 + abs(j - y), abs(y - i) + 1 + abs(x - j)])
        list1[i][j] = num

list2 = list(itertools.chain.from_iterable(list1))

for k in range(1,n):
    print(list2.count(k) // 2)

### FIXED CODE ###

n, x, y = map(int, input().split())
x -= 1
y -= 1

cnt_list = [0] * (n - 1)

for i in range(n):
    for j in range(n):
        if j <= i:
            continue
        
        #i < j,x < yのとき、i→y→x→jが最短になることはない
        num = min([j - i, abs(x - i) + 1 + abs(y - j)]) - 1 #距離 - 1、距離ゼロはif文で排除
        cnt_list[num] += 1

for n in cnt_list:
    print(n)
### BUGGY CODE ###


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

INF = 10 ** 20
dp = [INF] * n
dp[0] = 0

for i in range(1, n):
    hi = h[i]
    for j in range(max(i - k, 0), i):
        dp[i] = min(dp[i], dp[j] + abs(hi - h[j]))

print(dp[n-1])


### FIXED CODE ###

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

dp = [0] * n

for i in range(1, n):
    hi = h[i]
    s = max(i-k,0)
    dp[i] = min(dpj + abs(hi - hj) for dpj, hj in zip(dp[s:i], h[s:i]))
    
print(dp[-1])
### BUGGY CODE ###

x = list(map(int,input().split()))
a = 0
for i in range(x[0],x[1]+1):
    if i % x[2]==0:
        a = a+1
print(a)

### FIXED CODE ###

x = list(map(int,input().split()))
a = 0
if x[0]%x[2]==0:
    b = x[0]
else:
     b = ((x[0] // x[2])+1)*x[2]
c = (x[1]-b)//x[2] + 1

print(c)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heapify, heappop
import heapq
n,m,s,t =list(map(int,input().split()))

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))
snuke_cost = defaultdict(lambda :defaultdict(lambda :MAX_VAL))


for u,v,a,b in uvab:
    u=u-1
    v=v-1
    jpy_cost[u][v] = a
    jpy_cost[v][u] =a
    snuke_cost[u][v]=b
    snuke_cost[v][u]=b


# Dijktra's shortest path algorithm. Prints the path from source to target.


def dijkstra(adj, source):
    INF = MAX_VAL
    pred = [x for x in range(n)]
    dist = [INF for x in range(n)]
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while (PQ):
        u = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        u_dist = u[0]
        u_id = u[1]
        if u_dist == dist[u_id]:
            # if u_id == target:
            #    break
            for v in adj[u_id]:
                v_id = v
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v_id]:
                    dist[v_id] = dist[u_id] + w_uv
                    heapq.heappush(PQ, [dist[v_id], v_id])
                    pred[v_id] = u_id

    return dist


jpy_dijk =  dijkstra(jpy_cost,s-1)
snuke_dijk = dijkstra(snuke_cost,t-1)
#
# print(s,t)
# print(jpy_dijk)
# print(snuke_dijk)
# print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

#ord n
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    #都市  i で両替
    val = jpy_dijk[i]+ snuke_dijk[i]
    assert val < MAX_VAL
    min_val=min(min_val,val)
    res.append(min_val)
#ord n
for x in reversed(res):
    print(10**15-  x)


### FIXED CODE ###

from collections import defaultdict
from heapq import heapify, heappop
import heapq
n,m,s,t =list(map(int,input().split()))

MAX_VAL = 10**20
uvab =  [list(map(int,input().split())) for _ in range(m)]
jpy_cost = defaultdict(dict)
snuke_cost = defaultdict(dict)


for u,v,a,b in uvab:
    u=u-1
    v=v-1
    jpy_cost[u][v] = a
    jpy_cost[v][u] =a
    snuke_cost[u][v]=b
    snuke_cost[v][u]=b


# Dijktra's shortest path algorithm. Prints the path from source to target.


def dijkstra(adj, source):
    INF = MAX_VAL
    dist = [INF for x in range(n)]
    dist[source] = 0
    PQ = []
    heapq.heappush(PQ, [dist[source], source])

    while (PQ):
        u_dist,u_id = heapq.heappop(PQ)  # u is a tuple [u_dist, u_id]
        if u_dist == dist[u_id]:
            for v in adj[u_id]:
                w_uv = adj[u_id][v]
                if dist[u_id] + w_uv < dist[v]:
                    dist[v] = dist[u_id] + w_uv
                    heapq.heappush(PQ, [dist[v], v])
    return dist


jpy_dijk =  dijkstra(jpy_cost,s-1)
snuke_dijk = dijkstra(snuke_cost,t-1)
#
# print(s,t)
# print(jpy_dijk)
# print(snuke_dijk)
# print([jpy_dijk[i]+snuke_dijk[i] for i in range(n)])

#ord n
res = []
min_val = MAX_VAL
for i in reversed(range(n)):
    #都市  i で両替
    val = jpy_dijk[i]+ snuke_dijk[i]
    assert val < MAX_VAL
    min_val=min(min_val,val)
    res.append(min_val)
#ord n
for x in reversed(res):
    print(10**15-  x)
### BUGGY CODE ###

import bisect
import heapq

n=int(input())
a1=int(input())
alist=[a1]

for i in range(n-1):
    an=int(input())
    if an<=alist[0]:
        alist=[an]+alist
    else:
        index = bisect.bisect_left(alist, an)
        alist[index-1]=an

print(len(alist))

### FIXED CODE ###

import bisect

n=int(input())
a1=int(input())
alist=[]
for al in range(n-1):
    alist.append(-2)
alist.append(a1)

for i in range(n-1):
    an=int(input())
    #print(alist,an)
    index = bisect.bisect_left(alist, an)
    alist[index-1]=an

#print(alist)
index = bisect.bisect_left(alist, -1)
#print(index)
print(len(alist)- index)
### BUGGY CODE ###

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

uniq_items = []
for i in set(A):
    uniq_items.append(A.count(i))

if len(uniq_items) <= K:
    print("0")
else:
#     print(uniq_items)
#     print(sorted(uniq_items,reverse=True))
    print(sum(sorted(uniq_items,reverse=True)[K:]))

### FIXED CODE ###

from collections import Counter
N, K = map(int, input().split())
A = list(map(int, input().split()))

print(sum(sorted(Counter(A).values(),reverse=True)[K:]))
### BUGGY CODE ###

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

counter = 0

for i in range(n):
  if i == 0:
    counter += 1
  else:
    Min = min(p[:i+1])
  
    if Min == p[i]:
      counter += 1
    else:
      pass
  
print(counter)

### FIXED CODE ###

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

counter = 0
Min = p[0]

for i in range(n):
  if i == 0:
    counter += 1
  else:
    if p[i] <= Min:
      counter += 1
      Min = p[i]
  
print(counter)