inspirit941

def dfs(idx, price):
    global answer
    if idx >= len(days):
        answer = min(answer, price)
        return
    # 1일 이용권 결제
    if days[idx] == 0:
        dfs(idx+1, price)
    else:
        dfs(idx+1, price + (days[idx] * prices[0]))

inspirit941

import sys
import bisect
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

table = [arr[0]]
for idx in range(1, n):
    # 현재까지의 부분수열 최댓값보다 더 큰 값일 경우
    if arr[idx] > table[-1]:
        table.append(arr[idx])

inspirit941

import sys
from collections import defaultdict, deque

n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
connected = defaultdict(set)
for _ in range(m):
    parent, child = map(int, sys.stdin.readline().split())
    connected[parent].add(child)

inspirit941

import sys
from collections import deque
# F : 건물의 총 높이
# G : 목적지
# U : 위로 한 번에 이동할 수 있는 폭
# D : 아래로 한 번에 이동할 수 있는 폭
# 현재위치 = S.
F, S, G, U, D = map(int, sys.stdin.readline().split())

def bfs(start, end, up, down, F):

inspirit941

import sys
# 남 : 스위치번호가 자기 배수이면, 상태 바꾼다.
# 여 : 현 위치 중심으로 좌우대칭이면서 가장 많은 스위치를 포함하는 구간 전부 바꿈.
SPLITS = 20

# 좌우대칭이면서 가장 긴 거리 찾는 함수
def find_symmetric(arr, idx):
    r, l = idx - 1, idx + 1
    min_r, max_l = idx, idx
    while r > 0 and l < len(arr):

inspirit941

import sys
from copy import deepcopy
dirs = [(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1),(-1,1)]
maps = [[0 for _ in range(4)] for _ in range(4)]

fish_dict = dict()
y, x = 0, 0
for _ in range(4):
    arr = list(map(int, sys.stdin.readline().split()))
    for i in range(0, len(arr), 2):

inspirit941

import sys
from itertools import chain
r, c, t = map(int, sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(r)]
pos = 0
# 공기청정기 위치 확인
for y in range(r):
    if maps[y][0] == -1:
        pos = y
        break

inspirit941

# 블록이 직사각형인지 
def check_shape(start, color, row_num, board):
    y, x = start
    color = board[y][x]
    coord = set()
    color_cnt, black_cnt = 0, 0
    if row_num == 2 and y - 2 >= 0:
        # [1,#],
        # [1,#],
        # [1,1] 와 같은 형태

inspirit941

import sys
n, m, h = map(int, sys.stdin.readline().split())
table = [[0 for _ in range(n+2)]  for _ in range(h)]
# table[y][x] = x와 x+1이 y번째 row에서 연결되어 있다.
answer = 4
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    table[a-1][b] = 1

def check(maps):

inspirit941

import sys
from collections import deque
n, l = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
d = [0 for _ in range(n)]
window = deque()
for idx in range(n):
    # window의 마지막 값보다 input으로 넣을 값이 작은 경우
    # 최솟값은 어차피 input값이 될 것이므로, window에 굳이 넣을 필요가 없다
    while window and window[-1][1] > arr[idx]: