Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import math
import heapq

N, M = map(int, input().split())
MAX = math.inf

nodes = [[] for i in range(N+1)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    nodes[u].append(v)

S, T = map(int, input().split())
S -= 1
T -= 1

# init
d = [
    [math.inf for i in range(N)],
    [math.inf for i in range(N)],
    [math.inf for i in range(N)]
]
d[0][S] = 0
queue = []
heapq.heappush(queue, [0, 0, S])

while queue:
    p, m, n = heapq.heappop(queue)
    if m == 0 and n == T:
        print(int(p/3))
        quit()
    for to in nodes[n]:
        if d[(m+1) % 3][to] > d[m][n] + 1:
            d[(m+1) % 3][to] = d[m][n] + 1
            heapq.heappush(queue, [
                d[(m+1) % 3][to],
                (m+1) % 3,
                to
            ])

print(-1)


### FIXED CODE ###

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

N, M = map(int, input().split())
MAX = float("inf")

nodes = [[] for i in range(N+1)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    nodes[u].append(v)

S, T = map(int, input().split())
S -= 1
T -= 1

# init
d = [
    [MAX for i in range(N)],
    [MAX for i in range(N)],
    [MAX for i in range(N)],
]
d[0][S] = 0
queue = []
heapq.heappush(queue, [0, 0, S])

while queue:
    p, m, n = heapq.heappop(queue)
    if m == 0 and n == T:
        print(int(p/3))
        quit()
    for to in nodes[n]:
        if d[(m+1) % 3][to] > d[m][n] + 1:
            d[(m+1) % 3][to] = d[m][n] + 1
            heapq.heappush(queue, [
                d[(m+1) % 3][to],
                (m+1) % 3,
                to
            ])

print(-1)
num = raw_input()

print (num * num * num)

### FIXED CODE ###

a = input()
print a ** 3
def dfs(string, idx):
  tmp_s = string[0:idx]+"BCA"+string[idx+3:]
  # left
  if len(string[0:idx]) >= 1 and tmp_s[idx-1:idx+2] == "ABC":
    left_translated, left_count = dfs(tmp_s[:idx+2], idx-1)
  else:
    left_translated = tmp_s[:idx+2]
    left_count = 0
  #print("left:"+left_translated)
  if len(string[idx+3:]) >= 2 and tmp_s[idx+2:idx+5] == "ABC":
    right_translated, right_count = dfs(tmp_s[idx+2:], 0)
  else:
    right_translated = tmp_s[idx+2:]
    right_count = 0
    #print("right:"+right_translated)
  return left_translated + right_translated, left_count + right_count + 1


s = input()
total = 0
idx = s.find("ABC") 
while idx != -1:
  s, count = dfs(s, idx)
  total += count
  idx = s.find("ABC")
  
print(total)

### FIXED CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
def minus(n):
  return 128-n

s = input()
total = 0
new_s = s.replace("BC", "D")
new_s_list = list(new_s)
new_s_list.append("G")
tmp_start = 0
for i in range(len(new_s_list)):
  if new_s_list[i] in {'B', 'C', 'G'}:
    ppp = list(map(minus, map(ord, new_s_list[tmp_start:i])))
    bit = Bit(128)
    ans = 0
    for j, p in enumerate(ppp):
      bit.add(p, 1)
      ans += j + 1 - bit.sum(p)
    total += ans
    tmp_start = i+1

print(total)
N = int(input())
a = []
for i in range(N):
    a.append(map(int, input())
for i in range(N):
    v = a[i]
    j = i-1
    while j>=0 and a[j]>v:
        a[j+1] = a[j]
        j = j-1
        a[j+1] = v
    print(a) 


### FIXED CODE ###

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


for i in range(N):
    v = b[i]
    j = i-1
    while j>=0 and b[j]>v:
        b[j+1] = b[j]
        j = j-1
        b[j+1] = v
    print(" ".join([str(n) for n in b]))
N = int(input())
p = list(map(int,input().split()))
ret = 0
flag = 0
for i in range(len(p)):
  if i + 1 == p[i]:
    if flag == 0:
      ret += 1
      if p[i+1] == i+2:
        flag = 1
    else:
      flag = 0
print(ret)

### FIXED CODE ###

N = int(input())
p = list(map(int,input().split()))
ret = 0
flag = 0
for i in range(len(p)):
  if i + 1 == p[i]:
    if flag == 0:
      ret += 1
      if i < len(p)-1 and p[i+1] == i+2:
        flag = 1
    else:
      flag = 0
print(ret)
args = list(map(lambda x: int￼(x), input().split()))
N = args[0]
A = args[1]
B = args[2]
s = input()

a = 0
b = 0
for i in range(0, len￼(s)):
    if s[i] == 'a':
        if a + b < A + B:
            a = a + 1
            print('Yes')
        else:
            print('No')
    elif s[i] == 'b':
        if a + b < A + B and b < B:
            b = b + 1
            print('Yes')
        else:
            print('No')
    else:
        print('No')

### FIXED CODE ###

args = input().split()
N = int(args[0])
A = int(args[1])
B = int(args[2])
s = input()

a = 0
b = 0
for i in range(0, len(s)):
    if s[i] == 'a':
        if a + b < A + B:
            a = a + 1
            print('Yes')
        else:
            print('No')
    elif s[i] == 'b':
        if a + b < A + B and b < B:
            b = b + 1
            print('Yes')
        else:
            print('No')
    else:
        print('No')
x,y=map(int,input().split())

if (x+y)%3!=0:
    print(0)
    exit()
    
a=(2*y-x)//3
b=(2*x-y)//3

mod=10**9+7

F=[1]
for i in range(1,a+b+1):
    tmp=F[-1]*i
    F.append(tmp%mod)

Ia=pow(F[a],mod-2,mod)
Ib=pow(F[b],mod-2,mod)

ans=F[a+b]*Ia*Ib%mod
print(ans)


### FIXED CODE ###

x,y=map(int,input().split())

if (x+y)%3!=0:
    print(0)
    exit()
    
a=(2*y-x)//3
b=(2*x-y)//3

if a<0 or b<0:
    print(0)
    exit()

mod=10**9+7

F=[1]
for i in range(1,a+b+1):
    tmp=F[-1]*i
    F.append(tmp%mod)

Ia=pow(F[a],mod-2,mod)
Ib=pow(F[b],mod-2,mod)

ans=F[a+b]*Ia*Ib%mod
print(ans)
s = list(input())
t = ["A", "K", "I", "H", "A", "B", "A", "R", "A"]

if s == t:
    print("YES")
    exit()

if len(s) >= len(t):
    print("NO")
    exit()
    
if s[-1] != "A":
    s = s + ["A"]
for i in range(len(t)):
    if t[i] != s[i] and t[i] == "A":
        s.insert(i, "A")
        print(s)
if s == t:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

s = list(input())
t = ["A", "K", "I", "H", "A", "B", "A", "R", "A"]


if s[-1] != "A":
    s = s + ["A"]
for i in range(len(t)):
    if len(s) <= i: break
    if t[i] != s[i] and t[i] != "A":
        break
    if t[i] != s[i] and t[i] == "A":
        s.insert(i, "A")

if s == t:
    print("YES")
else:
    print("NO")
n,x = map(int,input().split())
l = list(map(int,input().split()))
L=0
for i in range(n):
    L += l[i]
    if L > x:
        print(i+1)
        return()

### FIXED CODE ###

n,x = map(int,input().split())
l = list(map(int,input().split()))
ans = 1
L=0
for i in range(n):
    L += l[i]
    if L <= x:
        ans+=1
print(ans)
import sys
sys.setrecursionlimit(10**5)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if (x,y) not in finished:
            finished.add((x,y))
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
black = 0
white = 0
#x,y渡すと、（ｈ、ｗ）に入ってるかどうか判定
def check(s,t):
    if (0 <=  s <= h - 1) and (0 <= t <= w - 1):
        return True
    else:
        return False
def bfs(que):
    finished = set()
    while que:
        x , y, color = que.popleft()
        if x+y*w not in finished:
            finished.add(x+y*w)
            for i in range(-1,2,1):
                for j in range(-1,2,1):
                    if abs(i) + abs(j) < 2 and check(y+j,x+i):
                        if (x+i)+(y+j)*w not in finished:
                            que.append([x+i,y+j,grid[y+j][x+i]])
                        if color != grid[y+j][x+i]:
                            adjacent_list[x+w*y].append((x + i)+w*(y + j))
def dfs(node):
    global white
    global black
    finished.add(node)
    y,x = divmod(node,w)
    if grid[y][x] == '#':
        black += 1
    else:
        white += 1
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i)
from collections import deque
h,w = map(int, input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
ans = 0
adjacent_list = [[] for i in range(h*w)]
"""
que = deque()
que.append([0,0,grid[0][0]])
bfs(que)
"""
for y in range(h):
    for x in range(w):
        for i in range(-1,2,1):
            for j in range(-1,2,1):
                if abs(i) + abs(j) < 2 and check(y+j,x+i):
                    if grid[y][x] != grid[y+j][x+i]:
                        adjacent_list[x+w*y].append((x + i)+w*(y + j))
#再び初期化
finished = set()
for i in range(h*w):
    #頂点iからdfsをする。黒と白をカウントしておいて最後にかける
    black = 0
    white = 0
    if i not in finished:
        dfs(i)
        ans += black * white
print(ans)
def signal(a,e):
	s=""
	for i in range(7):
		s+="0" if a[i]==e[i] else "1"
	return s

ref=["0111111","0000110","1011011","1001111","1100110","1101101","1111101","0100111","1111111","1101111"]
while 1:
	n=int(raw_input())
	if n==-1:break
	e="0000000"
	for i in range(n):
		a=ref[int(raw_input())]
		print signal(a,e)
		e=a

### FIXED CODE ###

ref=[63,6,91,79,102,109,125,39,127,111]
while 1:
	try:
		n=input()
		if n==-1:break
		e=0
		for i in range(n):
			a=ref[input()]
			print "{:07b}".format(a^e)
			e=a
	except:
		pass
from collections import deque
import numpy as np

H, W = map(int, input().split())
H += 2; W += 2
grid = []
grid.append("#" * W)
for h in range(H-2):
  grid.append("#" + input() + "#")
grid.append("#" * W)

INF = 10**9
ans = 0
for h in range(1, H-1):
  for w in range(1, W-1):
    
    if grid[h][w]=="#": continue

    dist = np.array([[INF]*W for i in range(H)])
    dist[h][w] = 0 
    q = deque([(h,w)])

    while(q):
      v_h, v_w = q.popleft()
      d_v = dist[v_h][v_w]
      for n_h, n_w in ((v_h, v_w-1),(v_h, v_w+1),(v_h-1, v_w),(v_h+1, v_w)):
        if grid[n_h][n_w]=="#": continue
        d_n = d_v + 1
        if d_n > dist[n_h][n_w]:
          continue
        dist[n_h][n_w] = d_n
        q.append((n_h,n_w))


    
      dist_m = max(x for x in dist.flatten() if x < INF)
      ans = max(ans, dist_m)

print(ans)

      


    

### FIXED CODE ###

from collections import deque
import numpy as np

H,W = map(int,input().split())
maze = [input() for _ in range(H)]

ans = 0
for x in range(H):
    for y in range(W):
        #壁からはスタートできない
        if maze[x][y] == "#":
            continue

        #初期化
        distance = [[0]*W for _ in range(H)]
        #start位置
        stack = deque([[x,y]])

        while stack:
            h,w = stack.popleft()
            for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
                new_h, new_w = h+i, w+j
                if new_h < 0 or new_w < 0 or new_h >= H or new_w >= W:
                    continue
                elif maze[new_h][new_w] != "#" and distance[new_h][new_w] == 0:
                    distance[new_h][new_w] = distance[h][w]+1
                    stack.append([new_h, new_w])

        #start位置は0で初期化
        distance[x][y] = 0
        ans = max(ans, np.max(distance))

print(ans)
import math
a,b=map(int,input().split())
print(math.ceil(a/(2b+1)))


### FIXED CODE ###

import math
a,b=map(int,input().split())
print(math.ceil(a/(b*2+1)))
s=raw_input()
n=len(s)
for i in xrange(n):
    if s[i]=="a":
        idx1=i
        break    
for i in xrange(n-1,0,-1):
    if s[i]=="z":
        idx2=i
        break
print idx2-idx1+1


### FIXED CODE ###

x=input()
if x<1200:
    print("ABC")
else:
    print("ARC")
cnt = {'AC':0, 'WA':0, 'TLE':0, 'RE':0}
for i in range(int(input()):
               s = input()
               cnt[s] += 1
for i in ['AC','WA','TLE','RE']:
               print(f'{i} x {cnt[i]}'
                     
               

### FIXED CODE ###

count = {'AC':0,'WA':0,'TLE':0,'RE':0}
for i in range(int(input())):
  count[input()] += 1

print(f"AC x {count['AC']}")
print(f"WA x {count['WA']}")
print(f"TLE x {count['TLE']}")
print(f"RE x {count['RE']}")
n,q=map(int,input().split())
s=list(input())
#print(s)
i=0
a=[]
x=0
while i!=len(s):
    if s[i]=="C" and a1==1:
        x=x+1
        a1=0
    elif s[i]=="A":
        a1=1
    else:
        a1=0
    i=i+1
    a.append(x)
#print(a)
i=0
while i!=q:
    l,r=map(int,input().split())
    i=i+1
    s=a[r-1]-a[l-1]
    print(s)

### FIXED CODE ###

n,q=map(int,input().split())
s=list(input())
#print(s)
i=1
a=[0]
x=0
while i!=n:
    if s[i-1]=="A":
        if s[i]=="C":
            x=x+1
    i=i+1
    a.append(x)

#print(a)
i=0
while i!=q:
  try:
    l,r=map(int,input().split())
    i=i+1
    s=a[r-1]-a[l-1]
    print(s)
  except:
      break
w,h = list(map(int, input().split()))
ws = []
hs = []
for i in range(w): ws.append(int(input()))
for i in range(h): hs.append(int(input()))

ws.sort(reverse = True)
hs.sort(reverse = True)

remainW = w
remainH = h
aliveW = [1 for i in range(w)]
aliveH = [1 for i in range(h)]

ans = 0
while(remainW>0 or remainH>0):
    #print(ans, remainW, remainH)
    costW = ws[remainW-1] * (remainH + 1)
    costH = hs[remainH-1] * (remainW + 1)
    if(costW > costH or remainW==0):
        ans += costH
        remainH-=1
    else:
        ans += costW
        remainW -= 1
print(ans)


### FIXED CODE ###


w,h = list(map(int, input().split()))
ws = []
hs = []
for i in range(w): ws.append(int(input()))
for i in range(h): hs.append(int(input()))

ws.sort(reverse = True)
hs.sort(reverse = True)

remainW = w
remainH = h
aliveW = [1 for i in range(w)]
aliveH = [1 for i in range(h)]

ans = 0
while(remainW>0 or remainH>0):
    #print(ans, remainW, remainH)
    costW = ws[remainW-1] * (remainH + 1)
    costH = hs[remainH-1] * (remainW + 1)
    if(remainH!=0 and (ws[remainW-1] > hs[remainH-1] or remainW==0)):
        ans += costH
        remainH = max(0,remainH-1)
    else:
        ans += costW
        remainW = max(0,remainW-1)
print(ans)
import sys
     
    s,w =(int(n) for n in input().split())
     
    if (s <= w):
        print("unsafe")
        sys.exit()
    else:
        print("safe")

### FIXED CODE ###


import sys
     
s,w =(int(n) for n in input().split())
     
if (s <= w):
        print("unsafe")
        sys.exit()
else:
        print("safe")
#Aです
import sys
input=lambda: sys.stdin.readline().rstrip()

def f(x,y):
  left,right=0,10**9
  while right-left>1:
    mid=(left+right)//2
    if x*mid+mid*(mid-1)//2<=y:
      left=mid
    else:
      right=mid
  return left

def f1(x,y):
  left,right=0,10**9
  while right-left>1:
    mid=(left+right)//2
    if x*mid+mid**2<=y:
      left=mid
    else:
      right=mid
  return left

def f2(x,y):
  left,right=0,10**9
  while right-left>1:
    mid=(left+right)//2
    if x*mid+mid*(mid+1)<=y:
      left=mid
    else:
      right=mid
  return left

t=int(input())
for _ in range(t):
  l,r=map(int,input().split())
  if l>=r:
    d=l-r
    ct=f(1,d)
    l-=ct*(ct+1)//2
    ct1=f1(ct,l)
    ct2=f2(ct,r)
    if ct1<=ct2:
      ans1=ct+2*ct1
      ans2=l-ct*ct1-ct1**2
      ans3=r-ct*ct1-ct1*(ct1+1)
    else:
      ans1=ct+2*ct2+1
      ans2=l-ct*(ct2+1)-(ct2+1)**2
      ans3=r-ct*ct2-ct2*(ct2+1) 
    print("Case #"+str(_+1)+": "+str(ans1)+" "+str(ans2)+" "+str(ans3))
  else:
    d=r-l
    ct=f(1,d)
    r-=ct*(ct+1)//2
    if l==r:
      ct1=f1(ct,l)
      ct2=f2(ct,r)
      if ct1<=ct2:
        ans1=ct+2*ct1
        ans2=l-ct*ct1-ct1**2
        ans3=r-ct*ct1-ct1*(ct1+1)
      else:
        ans1=ct+2*ct2+1
        ans2=l-ct*(ct2+1)-(ct2+1)**2
        ans3=r-ct*ct2-ct2*(ct2+1) 
      print("Case #"+str(_+1)+": "+str(ans1)+" "+str(ans2)+" "+str(ans3))
    
    else:
      ct1=f1(ct,r)
      ct2=f2(ct,l)
      if ct1<=ct2:
        ans1=ct+2*ct1
        ans3=r-ct*ct1-ct1**2
        ans2=l-ct*ct1-ct1*(ct1+1)
      else:
        ans1=ct+2*ct2+1
        ans3=r-ct*(ct2+1)-(ct2+1)**2
        ans2=l-ct*ct2-ct2*(ct2+1) 
      print("Case #"+str(_+1)+": "+str(ans1)+" "+str(ans2)+" "+str(ans3))

### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
s,w=map(int,input().split())
if w>=s:
  print("unsafe")
else:
  print("safe")
import sys
sys.setrecursionlimit(900000000)
def knap(n,w,weight,value,dp):
    #print(n,":",w,":",len(dp),":",len(dp[n]))
    x=dp[n][w]
    if x!=-1:
        return x
    if n==0:
        dp[n][w]=0
        return 0
    if w==0:
        dp[n][w]=0
        return 0
    if w-weight[n-1]<0:
        tmp2=knap(n-1,w,weight,value,dp)
        dp[n][w]=tmp2
        return tmp2
    tmp1=knap(n-1,w-weight[n-1],weight,value,dp)+value[n-1]
    tmp2=knap(n-1,w,weight,value,dp)
    if tmp1>=tmp2:
        dp[n][w]=tmp1
        return tmp1
    else:
        dp[n][w]=tmp2
        return tmp2  
def main():
    n,W=map(int,input().split())
    weight=[]
    value=[]
    for i in range(n):
        a,b=map(int,input().split())
        weight.append(a)
        value.append(b)
    dp=[[-1]*(W+1)]*(n+1)
    print(knap(n,W,weight,value,dp))
    return 0
main()

### FIXED CODE ###

N,W=map(int,input().split())
w=[]
v=[]
maxV=0
for i in range(N):
    a,b=map(int,input().split())
    if maxV<b:
        maxV=b
    w.append(a)
    v.append(b)
#dp[n個目のアイテムまでで][V以上を達成する]=最小のw
#dp[0][v]=inf ゼロ個でｖは無理なので
#dp[0][0]=0と初期化する
#だからiの時dp[i][v]=min(dp[i-1][v],dp[i-1][V-v[i-1]]+w[i])である<-i-1なのはvとかにはゼロ個とかないので
#V-v[i]<0ならば、とれないので前者になるね！！
#これをi=0(は初期化でする)->nまでおこない、各iについてはとりうる最大のValueを考えるが
#これは最大で各アイテムについて最大のVがあってこれにアイテム数Nを掛けたものである
#つまりdpのサイズはdp[0->N][0->maxV*N]をとればよい

dp=[[float("inf") for i in range(maxV*(N+1))] for j in range(N+1)]
dp[0][0]=0

for i in range(1,N+1):
    for val in range(maxV*N+1):
        tmp1=dp[i-1][val]#とらない
        if val-v[i-1]<0:#この時、iこめの価値がおおきいので、これをとるだけで達成してしまう
            tmp2=w[i-1]#i=1の時、dp[0][val]=inf
        else:#i=1の時val-v[0]>0で無限になるので
            tmp2=dp[i-1][val-v[i-1]]+w[i-1]#
        res=min(tmp1,tmp2)
        dp[i][val]=res
#ここでW以下となるvalの最大値をたんさくする
max=0
for value in range(len(dp[N])):
    if dp[N][value]<=W:
        if value>max:
            max=value
print(max)
# -*- coding: utf-8 -*-
import sys

class Tree:
    def __init__(self, v):
        self.v = 0
        self.counter = 0
        self.leaves = []

[n, q] = [int(x) for x in sys.stdin.readline().rstrip().split()]

a = [0] * (n-1)
b = [0] * (n-1)
for i in range(n-1):
    [a[i], b[i]] = [int(x) for x in sys.stdin.readline().rstrip().split()]
p = [0] * q
x = [0] * q
for i in range(q):
    [p[i], x[i]] = [int(x) for x in sys.stdin.readline().rstrip().split()]

trees = [Tree(0)]
tree_dict = {}

for i in range(1,n+1):
    tree = Tree(i)
    trees.append(tree)
    tree_dict[i] = tree
    
root = tree_dict[1]
        
for i in range(n-1):
    tree_dict[a[i]].leaves.append(tree_dict[b[i]])

def rec_add(t: Tree, x: int):
    t.counter += x
    for child in t.leaves:
        rec_add(child, x)

for i in range(q):
    rec_add(tree_dict[p[i]], x[i])

print(' '.join(list(map(lambda x: str(x.counter), trees[1:]))))


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

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

counts = [0] * (n+1)
adjs = {a: [] for a in range(1,n+1)}

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

costs = [[int(x) for x in input().split()] for i in range(q)]

for cost in costs:
    counts[cost[0]] += cost[1]

visited = set()
queue = deque()
queue.append(1)

while len(queue) > 0:
    a = queue.popleft()
    visited.add(a)
    for b in adjs[a]:
        if b in visited:
            continue
        counts[b] += counts[a]
        queue.append(b)

for c in counts[1:]:
    print(c, end=" ")
print()
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = deque([0, 0, num + 1, num + 1])
    # ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        # bisect.insort_left(ind_list, ori_ind)
        # add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        add_ind = -1
        ind_list.insert(add_ind, ori_ind)
        # print(add_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: x[0])

    left = [0, 0] + [i + 1 for i in range(num)]
    right = [i + 1 for i in range(num)] + [num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        l1 = left[ori_ind]
        l2 = left[l1]
        r1 = right[ori_ind]
        r2 = right[r1]

        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

        right[l1] = r1
        left[r1] = l1

    print(ans)


if __name__ == '__main__':
    main()
N,M = map(int,input().split())

T = (1900*M)+(100*(N-M))
C = [pow(2,M),pow(2,M)-1]

if M==4: M_set[1]=3

a = T*C[0]
if a%C[1]==0:
    a = a//C[1]
    print(a)
else:
    print(a)

### FIXED CODE ###

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

T = (1900*M)+(100*(N-M))
C = [pow(2,M),pow(2,M)-1]

print(T*C[0])
N,K = map(int,input().split())
price = list(map(int,input().split()))
priceN = sorted(price)
total = 0
for i in range(K):
  total += priceN[i]
price(total)

### FIXED CODE ###

N,K = map(int,input().split())
price = list(map(int,input().split()))
priceN = sorted(price)
total = 0
for i in range(K):
  total += priceN[i]
print(total)
N, K = map(int, input().split())
tmp = N


if K > N:
    print(N)
    exit()

a = abs(N - K)
ans1 = N % a
ans2 = abs((N % a) - a)
if K == 1:
    print(0)
else:
    print(min(ans1, ans2))



### FIXED CODE ###

N, K = map(int, input().split())
tmp = N % K
print(min(tmp, abs(tmp - K)))
n = long(input())
x = [long(i) for i in input().split()]
sortx = sorted(x)

mid_left = sortx[(n//2)-1]
mid_right = sortx[(n//2)]

for i in range(n):
    if sortx[i] <= mid_left:
        print(mid_right)
    else:
        print(mid_left)

### FIXED CODE ###

n = int(input())
x = [int(i) for i in input().split()]
sortx = sorted(x)

mid_left = sortx[(n//2)-1]
mid_right = sortx[(n//2)]

for i in range(n):
    if x[i] <= mid_left:
        print(mid_right)
    else:
        print(mid_left)