ShinYoung-hwan

import sys

input = lambda: sys.stdin.readline().rstrip()

if __name__ == "__main__":
    N = int(input()) # 수열 A의 원소의 개수
    A = list(map(int, input().split())) # 수열

    # solve 
    dp = [ 1 ] * N # A[i]를 포함하는 LIS의 길이

ShinYoung-hwan

import sys

input = lambda: sys.stdin.readline().rstrip()

MOD = 1000

def mat_mul(m1: list, m2: list, N: int):
    # A * B
    new_matrix = [ [0] * N for _ in range(N) ]
    for r in range(N):

ShinYoung-hwan

import sys

input = lambda: sys.stdin.readline().rstrip()

def is_in(string: list, word: str, word_len: int) -> bool:
    # string 내부에 word가 있는지 확인한다.
    if len(string) < word_len: return False
    
    for i in range(1, word_len+1):
        if string[-i] != word[-i]:

ShinYoung-hwan

import sys

input = lambda: sys.stdin.readline().rstrip()

# board에서 (r, c) 위치에 퀸을 놓을 때 valid 한지 
def is_valid(board, r, c):
    for i in range(r):
        prev = board[i]
        
        # 같은 열에 존재

ShinYoung-hwan

import sys

input = lambda: sys.stdin.readline().rstrip()

def solve(stickers, n):
    if n == 1: # n이 (2*1) 크기의 스티커
        return max(stickers[0][0], stickers[1][0])
    
    # n >= 2인 경우
    # i번째까지의 최대 누적합

ShinYoung-hwan

import sys

input: lambda: sys.stdin.readline().rstrip()

def get_lcs_len(s1: str, s2: str):
    # 두 문자열의 최장 공통 부분 수열의 길이 구하기
    ls1 = len(s1)
    ls2 = len(s2)
    
    lcs = [ [ 0 ] * (ls1+1) for _ in range(ls2+1) ] # 각 문자열까지의 최장 공통 부분 수열의 길이

ShinYoung-hwan

import sys

sys.setrecursionlimit(10**5)

inputs = lambda: sys.stdin.readlines()

def postorder(preorder, l, r):
    # 전위 순회 결과(CLR)를 후위 순회 결과(LRC)로 변경하기
    if l > r: return
    

ShinYoung-hwan

import sys

from collections import deque

input = lambda: sys.stdin.readline().rstrip()

dr = [ -1, 1, 0, 0 ]
dc = [ 0, 0, -1, 1 ]

def is_melt(paper, r0, c0):

ShinYoung-hwan

import sys

input = lambda: sys.stdin.readline().rstrip()

def star(n, r0, c0):
    # paper에 별을 찍어준다.
    global paper
    # 기저케이스
    if n == 3:
        paper[r0][c0] = '*'

ShinYoung-hwan

import sys

from collections import deque

input = lambda: sys.stdin.readline().rstrip()
inputs = lambda: sys.stdin.readlines()

dr = [ -1, 1, 0, 0 ]
dc = [ 0, 0, -1, 1 ]