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

from heapq import heappop, heappush
n = int(input())
INF = 10**13
g = [[INF for __ in range(n)] for _ in range(n)]

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


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [INF] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in enumerate(edges[u]):
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


q, k = map(int, input().split())
d = dijkstra(k-1, n, g)

for _ in range(q):
    x, y = map(int, input().split())
    print(d[x-1]+d[y-1])


### FIXED CODE ###

from heapq import heappop, heappush
n = int(input())
g = [[] for _ in range(n)]

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


def dijkstra(s, n, edges):
    # edges[i][j] : the cost of i→j
    # import 'heap'
    d = [10**18] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist_u, u = heappop(q)
        if d[u] < dist_u:
            continue
        for v, c in edges[u]:
            if d[v] > dist_u + c:
                d[v] = dist_u + c
                heappush(q, (d[v], v))
    return d


q, k = map(int, input().split())
d = dijkstra(k-1, n, g)

for _ in range(q):
    x, y = map(int, input().split())
    print(d[x-1]+d[y-1])
### BUGGY CODE ###

S = input()
mod = 10 ** 9 + 7
dp = [0] * 13
dp[0] = 1
for s in S:
    d = [0] * 13
    if s == '?':
        for i in range(13):
            for j in range(10):
                d[(10*i + j) % 13] += dp[i]
    else:
        for i in range(13):
            d[(10*i + int(s)) % 13] += dp[i]
    dp = [x % mod for x in d]
print(d[5] % mod)


### FIXED CODE ###

S = input()
mod = 10 ** 9 + 7
dp = [0] * 13
dp[0] = 1
for s in S:
    d = [0] * 13
    if s == '?':
        for i in range(13):
            for j in range(10):
                d[(10*i + j) % 13] += dp[i]
    else:
        for i in range(13):
            d[(10*i + int(s)) % 13] += dp[i]
    dp = [x % mod for x in d]
print(d[5] % mod)
### BUGGY CODE ###

# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import combinations
def run():
    N = int(input())
    A = list(map(int, sysread().split()))
    A = [(idx, val) for idx, val in enumerate(A, 1)]
    ret = 0
    for (i,Ai), (j,Aj) in combinations(A, 2):
        if abs(i-j) == Ai+Aj:
            ret += 1

    print(ret)

if __name__ == "__main__":
    run()

### FIXED CODE ###

# coding: utf-8
import sys
sysread = sys.stdin.readline

def run():
    N = int(input())
    A = list(map(int, sysread().split()))


    A = [(idx, val) for idx, val in enumerate(A, 1) if val < N]

    ret = 0
    store = [0] * N
    for idx, val in A:
        if idx - val > 0:
            ret += store[idx - val]
        try:
            store[idx + val] += 1
        except:
            continue
    print(ret)

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

import bisect

n = int(input())

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

A.sort(); B.sort(); C.sort()

ans = 0


for a in range(n):
    for b in range(n-1,-1,-1):
        if A[a] >= B[b]:
            break
        index = bisect.bisect_left(C, B[b]+1)
        ans += n-index
        
    

print(ans)




### FIXED CODE ###

import bisect

n = int(input())

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

A.sort(); B.sort(); C.sort()

ans = 0
b_li = [0 for i in range(n)]

for b in range(n):    
    index = bisect.bisect_left(C, B[b]+1)
    b_li[b] = n-index

for b in range(n-2,-1,-1):
    b_li[b] += b_li[b+1]
b_li.append(0)

for a in range(n):    
    index = bisect.bisect_left(B, A[a]+1)

    ans += b_li[index]
    
        
    

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

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

list1 = []
count = 0
for i in range(Q):
    l,r = map(int,input().split())
    l = l - 1
    w_string = S[l:r]
    for j, k in enumerate(w_string):
        if 'AC' in w_string[j:j+2]:
            count = count + 1
    list1.append(count)
    count = 0

for i in list1:
    print(i)


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

s = input()
q = int(input())

counter = 0
for i in range(q):
    x = input().split()

    if str(x[0]) == '1':
        counter += 1

    else:
        if counter % 2 != 0:
            s = s[::-1]
            counter = 0
        if str(x[1]) == '1':
            s = str(x[2]) + s

        else:
            s = s + str(x[2])

if counter % 2 != 0:
    s = s[::-1]
print(s)


### FIXED CODE ###

s = input()
q = int(input())
qs = [input().split() for i in range(q)]
n = False
left= right = ""
for operation in qs:
    if operation[0] == '1':
        n = not n
    if operation[0] == '2':
        t , f, c = operation
        f = int(f)
        if n:
            f = 1 if f != 1 else 2
        if f == 1:
            left=c+left
        elif f == 2:
            right+=c
s = left+s+right
print(s[::-1] if n else s)
### BUGGY CODE ###

# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

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

ans = ""
for i in range(N):
    ans += str(list_A.index(i+1) + 1)
    ans += " "
ans = ans.strip()
print(ans)


### FIXED CODE ###

# n, m, l = map(int, input().split())

# list_n = list(map(int, input().split()))

# n = input()
# list = [input() for i in range(N)

# list = [[i for i in range(N)] for _ in range(M)]

N = int(input())
list_A = list(map(int, input().split()))
student = list(range(N))

student.sort(key=lambda i: list_A[i])

ans = ""
for i in range(N):
    ans += str(student[i]+1) + " "
    # print(ans)
ans = ans.strip()

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

import sys,collections
input = sys.stdin.readline

s = input().rstrip()
K = int(input())
ls = len(s)
cs = collections.deque()
for i in range(ls):
    for j in range(i+1,ls+1):
        cs.append(s[i:j])
os = sorted(cs)
count = 0
lis = []
for i in os:
    if i not in lis:
        lis.append(i)
        count +=1
    else:
        continue
    if count == K:
        print(i)
        exit()
    


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

s = input().rstrip()
K = int(input())
ls = len(s)
cs = collections.deque()
for i in range(ls):
    for j in range(i+1,i+1+K):
        cs.append(s[i:j])
os = sorted(cs)
count = 0
lis = []
for i in os:
    if i not in lis:
        lis.append(i)
        count +=1
    else:
        continue
    if count == K:
        print(i)
        exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v,s):
    global c
    if c:
        return
    seen[v]=True
    for nv in G[v]:
        if seen[nv]:
            if nv in s:
                c=True
                return
            continue
        dfs(nv,s|{v})
    srted.append(v)
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
c=False
seen=[False]*P
srted=[]
for i in range(P):
    if not seen[i]:
        dfs(i,set())
if c:
    print(-1)
    exit()
dp=[1]*P
for v in reversed(srted):
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))

### FIXED CODE ###

from collections import deque
def tsort():
    que=deque([i for i,c in enumerate(In) if c==0])
    l=[]
    while que:
        v=que.popleft()
        l.append(v)
        for nv in G[v]:
            In[nv]-=1
            if In[nv]==0:
                que.append(nv)
    if len(l)!=P:
        print(-1)
        exit()
    return l
    
def setID():
    t=0
    ID=[[None]*N for i in range(N)]
    for i in range(N):
        for j in range(i+1,N):
            ID[i][j]=t
            t+=1
    for i in range(N):
        for j in range(N-1):
            a,b=i,A[i][j]
            if(a>b):
                a,b=b,a
            A[i][j]=ID[a][b]
    return t
N=int(input())
A=[list(map(lambda x:int(x)-1,input().split())) for i in range(N)]
P=setID()
In=[0]*P
G=[[] for i in range(P)]
for i in range(N):
    for j in range(N-2):
        G[A[i][j]].append(A[i][j+1])
        In[A[i][j+1]]+=1
srted=tsort()
dp=[1]*P
for v in srted:
    for nv in G[v]:
        dp[nv]=max(dp[nv],dp[v]+1)
print(max(dp))
### BUGGY CODE ###

n = int(input())
nums = list(map(int, input().split()))
for i in range(n):
    temp = list(nums)
    temp.pop(i)
    temp = sorted(temp)
    print(temp[(n+1)//2-1])


### FIXED CODE ###

n = int(input())
a = [int(x) for x in input().split()]
x = sorted(a)
m1 = x[n // 2]
m2 = x[n // 2 - 1]
for i in range(n):
    if a[i] < m1: print(m1)
    else: print(m2)
### BUGGY CODE ###

r =10000001
p = [1]*r
p[0]= p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0 for j in range(2*i,r,i)]
		
while 1:
	try:
		n = input()
		if n == 0: break
		n -= 1-n%2
		while any(not p[n-i] for i in [0,2,6,8]):
			n -= 2
		print n
	except:
		pass

### FIXED CODE ###

ref = [[[10,8],[4,4]],[[10,2],[4,2]]]
r =10000001
p = [1]*r
p[0]= p[1] = 0
for i in range(int(r**0.5)):
	if p[i]:
		p[2*i::i] = [0]*len(p[2*i::i])
		
while 1:
	try:
		n = input()
		if n == 0: break
		n -= 1-n%2
		while any(not p[n-i] for i in [0,2,6,8]):
			n -= ref[p[n-2]][p[n-6]][p[n-8]]
		print n
	except:
		pass
### BUGGY CODE ###

n, m = map(int, input().split())
li = [0]*(n+1)
flag = 1
for _ in range(m):
    a, b = map(int, input().split())
    if li[a] and li[b]:
        if li[a] != li[b]:
            x = li[b]
            for i in range(len(li)):
                if li[i] == x:
                    li[i] = li[a]
    elif li[a] or li[b]:
        s = max(li[a],li[b])
        li[a] = s
        li[b] = s
    else:
        li[a] = flag
        li[b] = flag
        flag += 1
for i in range(len(li)):
    if li[i] == 0:
        li[i] = -i
from collections import Counter
result = Counter(li)
print(result.most_common(1)[0][1])


### FIXED CODE ###

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

class unionfind():
    def __init__(self,n):
        self.li = [i for i in range(n+1)]
        self.group = [1]*(n+1)

    def find(self, x):
        while self.li[x]!=x:
            x = self.li[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return;
        elif x>y:
            self.li[y] = x
            self.group[x] += self.group[y]
        else:
            self.li[x] = y
            self.group[y] += self.group[x]
x = unionfind(n)
ans = 0
for _ in range(m):
    a,b = map(int,input().split())
    x.union(a,b)
print(max(x.group))
### BUGGY CODE ###

from heapq import *
import sys
input=sys.stdin.readline

N,M=map(int,input().split())
G=[set() for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    G[u].add(v)
S,T=map(int,input().split())
A=[set() for i in range(N)]
for i in range(N):
    for v in G[i]:
        A[i]=A[i] | G[v]
B=[set() for i in range(N)]
for i in range(N):
    for v in A[i]:
        B[i]=B[i] | G[v]
C=[[] for i in range(N)]
for i in range(N):
    for j in B[i]:
        C[i].append([j,1])
INF=10**9+7
def dijkstra(G,s):

  d=[INF]*N
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d
d=dijkstra(C,S-1)
if d[T-1]==INF:
  print(-1)
else:
  print(d[T-1])


### FIXED CODE ###

from heapq import *
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G=[[] for i in range(3*N)]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    G[3*u+0].append([3*v+1,0])
    G[3*u+1].append([3*v+2,0])
    G[3*u+2].append([3*v+0,1])
S,T=map(int,input().split())
INF=10**9+7
def dijkstra(G,s):

  d=[INF]*(3*N)
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d
d=dijkstra(G,(S-1)*3)
if d[(T-1)*3]==INF:
  print(-1)
else:
  print(d[(T-1)*3])
### BUGGY CODE ###

N = int(input())
S = input()
r = []
g = []
b = []

def greedy(s, l1, l2):
  total = 0
  for i in l1:
    for j in l2:
      if s < i < j:
        if i - s != j - i:
          total += 1
  return total

for i in range(N):
  if S[i] == 'R':
    r.append(i)
  elif S[i] == 'G':
    g.append(i)
  else:
    b.append(i)

total = 0
for i in range(N):
  if S[i] == 'R':
    total += greedy(i, g, b)
    total += greedy(i, b, g)
  elif S[i] == 'G':
    total += greedy(i, b, r)
    total += greedy(i, r, b)  
  else:
    total += greedy(i, r, g)
    total += greedy(i, g, r)
print(total)  
      

### FIXED CODE ###

N = int(input())
S = input()
r,g,b = 0,0,0
for i in S:
  if i == 'R':
    r += 1
  elif i == 'G':
    g += 1
  else:
    b += 1
minus = 0
for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = 2 * j - i
    if k >= N:
      continue
    if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
      minus += 1
print(r*g*b - minus)
### BUGGY CODE ###



import numpy as np
N = int(input())
A=np.array([])
for i in range(N):
    A=np.append(A, int(input()) )

max_index=np.argmax(A)
a_max=int(A[max_index])
a_second=int(np.amax(np.delete(A,max_index)))
A[:]=a_max
A[max_index]=a_second
for a in A:
    print(int(a))

### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array([int(input()) for i in range(N)])

max_index=np.argmax(A)
a_max=int(A[max_index])
a_second=int(np.amax(np.delete(A,max_index)))
A[:]=a_max
A[max_index]=a_second
for a in A:
    print(int(a))
### BUGGY CODE ###

n = int(input())
L = tuple(map(int, input().split()))
L = sorted(L, reverse=True)

counts = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        cc = a - L[j]
        left = j
        right = n
        while right - left > 1:
            mid = (right+left)//2
            if L[mid] > cc:
                left = mid
            else:
                right = mid
        counts += left - j
print(counts)

### FIXED CODE ###

n = int(input())
L = tuple(map(int, input().split()))
L = sorted(L, reverse=True)

counts = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        cc = a - L[j]
        left = j
        right = n
        while right - left > 1:
            mid = (right+left)//2
            if L[mid] > cc:
                left = mid
            else:
                right = mid
        counts += left - j
print(counts)
### BUGGY CODE ###

import itertools
import fractions
k = int(input())
nums = [i for i in range(1,k+1)]
alist = []
ans = 0
for balls in itertools.product(nums, repeat=3):
  alist.append(balls)
for i in alist:
  ans += fractions.gcd(i[0],fractions.gcd(i[1],i[2]))
print(ans)

### FIXED CODE ###

import math
ans = 0
k = int(input())
for i in range(1,k+1):
  for j in range(1,k+1):
    for l in range(1,k+1):
      ans += math.gcd(i,math.gcd(j,l))
print(ans)
### BUGGY CODE ###

K,S=map(int, input().split(' '))

count = 0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k == S:
                count += 1

print(count)


### FIXED CODE ###

K,S=map(int, input().split(' '))

count = 0
for i in range(K+1):
    for j in range(K+1):
        k = S-(i+j)
        if 0<= k <= K:
            count += 1

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

import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import itertools
#input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
def ri():
    return list(map(int, input().split()))
def rs():
    return list(input().strip())

n,m = ri()
edge=[[0]*n for i in range(n)]
for i in range(m):
    a, b = ri()
    a+=-1
    b+=-1
    edge[a][b]=1
    edge[b][a]=1

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    while len(q):
        
        now, p, d = q.popleft()
        if now==p:
            continue
        if visited[now]==1:
            continue
        
        ans[now]=p+1
        dis[now]=d+1
        visited[now]=1
        for i in range(n):
            if edge[now][i]==1 and visited[i]==0:
                q.append((i, now, dis[now]))
                
                visited[i]==1
bfs(0)

flag=True
for i in range(n):
    if visited[i]==0:
        flag=False
if flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i])
else:
    print("No")

### FIXED CODE ###

import sys
#import time
#import copy
from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import itertools
#input = sys.stdin.readline
sys.setrecursionlimit(10**6)
 
def ri():
    return list(map(int, input().split()))
def rs():
    return list(input().strip())

n,m = ri()
edge=[[] for _ in range(n)]
for i in range(m):
    a, b = ri()
    a+=-1
    b+=-1
    edge[a].append(b)
    edge[b].append(a)

visited=[0]*n
dis = [0]*n
ans=[0]*n
def bfs(now, p=-1):
    q = deque([])
    q.append((now, p, -1))
    while len(q):
        now, p, d = q.popleft()
        dis[now] = d+1
        visited[now]=1
        ans[now]=p+1
        
        for e in edge[now]:
            if visited[e]==1:
                continue
            if e==now:
                continue
            q.append((e, now, dis[now]))
            visited[e]=1
        
        
        
        
bfs(0)
flag=True
for i in range(n):
    if visited[i]==0:
        flag=False
if flag:
    print("Yes")
    for i in range(1,n):
        print(ans[i])
else:
    print("No")
### BUGGY CODE ###

s = input()
mod = [0] * 2019
mod[0] = 1
d = 1
n = 0
for i in reversed(s):
    n += int(i) * d
    d *= 10
    mod[n % 2019] += 1
print(sum(i*(i-1)//2 for i in mod))


### FIXED CODE ###

s = input()
mod = [0] * 2019
mod[0] = 1
d = 1
n = 0
for i in reversed(s):
    n += int(i) * d
    n %= 2019
    d *= 10
    d %= 2019
    mod[n % 2019] += 1
print(sum(i*(i-1)//2 for i in mod))
### BUGGY CODE ###

N = int(input())
K = int(input())

res = 0
if K == 1:
    for i in range(1,10):
        for j in range(len(str(N))):
            if i*10**j <= N:
                res += 1
if K == 2:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for j1 in range(len(str(N))-1):
                for j2 in range(len(str(N))-1-j1):
                    if i1*10**(j1+j2+1)+i2*10**j2 <= N:
                        res += 1

if K == 3:
    for j1 in range(len(str(N))-2-1):
        for j2 in range(len(str(N))-2-1-j1):
            for j3 in range(len(str(N))-2-1-j1-j2):
                res += 1
    res = res * (9**3)
    
    for i1 in range(1,10):
        for i2 in range(1,10):
            for i3 in range(1,10):
                for j1 in range(len(str(N))-2):
                    for j2 in range(len(str(N))-2-j1):
                        j3 = len(str(N))-2-j1-j2-1
                        if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N:
                            res += 1

print(res)


### FIXED CODE ###

N = int(input())
K = int(input())

res = 0
if K == 1:
    for i in range(1,10):
        for j in range(len(str(N))):
            if i*10**j <= N:
                res += 1
if K == 2:
    for i1 in range(1,10):
        for i2 in range(1,10):
            for j1 in range(len(str(N))-1):
                for j2 in range(len(str(N))-1-j1):
                    if i1*10**(j1+j2+1)+i2*10**j2 <= N:
                        res += 1

if K == 3:
    for j1 in range(len(str(N))-2-1):
        for j2 in range(len(str(N))-2-1-j1):
            for j3 in range(len(str(N))-2-1-j1-j2):
                res += 1
    res = res * (9**3)
    
    for j1 in range(len(str(N))-2):
        for j2 in range(len(str(N))-2-j1):
            j3 = len(str(N))-2-j1-j2-1
            for i1 in range(1,10):
                for i2 in range(1,10):
                    for i3 in range(9,0,-1):
                        if i1*10**(j1+j2+j3+2)+i2*10**(j2+j3+1)+i3*10**+j3 <= N:
                            res += i3
                            break

print(res)
### BUGGY CODE ###

#ALDS1_5-B Merge Sort
from collections import deque

def merge(A,B):
    ans = deque()
    count = 0
    while(True):
        if len(A)==0 and len(B) == 0:
            break
        elif len(A) == 0:
            ans.append(B.popleft())
        elif len(B) == 0:
            ans.append(A.popleft())
        elif A[0] > B[0]:
            ans.append(B.popleft())
        else:
            ans.append(A.popleft())
        count+=1
    return (ans,count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.pop()
    if(len(d)>2):
        mid = len(d)//2
        div.appendleft(d[:mid])
        div.appendleft(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.appendleft(d[::-1])
        else:
            mer.appendleft(d)
        count+=2
    else:
        mer.appendleft(d)
        
while(len(mer)>1):
    A = deque(mer.popleft())
    B = deque(mer.popleft())
    ret = merge(A,B)
    mer.append(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)


### FIXED CODE ###

from collections import deque

def merge(A,B):
    ans = [0]*(len(A)+len(B))
    count=i=j=0
    A+=[10**9+1]
    B+=[10**9+1]
    for k in range(len(ans)):
        if A[i]<B[j]:
            ans[k]=A[i]
            i+=1
        else:
            ans[k]=B[j]
            j+=1
        count+=1
    return (ans,count)

n = int(input())
S = [int(i) for i in input().split()]
div = deque([S])
mer = deque()
count = 0
while(len(div)>0):
    d = div.popleft()
    if(len(d)>2):
        mid = len(d)//2
        div.append(d[:mid])
        div.append(d[mid:])
    elif(len(d)==2):
        if d[0] > d[1]:
            mer.append(d[::-1])
        else:
            mer.append(d)
        count+=2
    else:
        mer.append(d)
        
while(len(mer)>1):
    A = mer.pop()
    B = mer.pop()
    ret = merge(A,B)
    mer.appendleft(ret[0])
    count+=ret[1]
    
ans = ""
for i in ret[0]:
    ans += str(i) + " "
print(ans[:-1])
print(count)
### BUGGY CODE ###

n, k = map(lambda x: int(x), input().split())
list_a =  list(map(lambda x: int(x), input().split()))

score = 1
for each in list_a[0:k]:
    score *= each
    
for i, next_score in enumerate(list_a[k:]):
    score_before = score
    score = score_before * next_score / list_a[i]
    if score > score_before:
        print('Yes')
        continue
    print('No')

### FIXED CODE ###

n, k = map(lambda x: int(x), input().split())
list_a =  list(map(lambda x: int(x), input().split()))

band_score = 1
    
for i, score in enumerate(list_a[k:]):
    if list_a[i] < score:
        print('Yes')
        continue
    print('No')
### BUGGY CODE ###

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

count = 0
for i in range(1, n + 1):
  if min(numList[:i]) == numList[i-1]:
    count += 1
print(count)

### FIXED CODE ###

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

count = 0
minNum = 10 ** 6
for i in range(1, n + 1):
  if minNum > numList[i-1]:
    minNum = numList[i-1]
    count += 1
print(count)