1874.py

# 스택 수열
# 시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
# 2 초	128 MB	181707	72910	50420	38.750%
# 문제
# 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 
# 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 
# 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

# 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 
# 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 
# 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 
# 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.


# 입력
# 첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 
# 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 
# 물론 같은 정수가 두 번 나오는 일은 없다.

# 출력
# 입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. 
# push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.


# 1. 문제분석
# 스택의 원리를 정확히 알고 있는지 물어보는 문제이다.
# 스택의 push, pop 연산, 후입선출 개념을 이해한다면 풀 수 있다.
# 여기에 데이터들이 오름차순 정렬이라는 것을 추가로 유념하자.

# 스택 연산 수행법
# case1. 현재 수열의 값 >= 자연수
# 1) 자연수를 1씩 증가시키며 자연수를 스택에 push
# 2) push이후 수열을 출력하기 위해 마지막에 1번 pop

# case2. 현재 수열의 값 < 자연수
# 1) pop으로 스택에 있는 데이터를 꺼냄
# 2) 이때 꺼낸 데이터가 현재 수열 값이거나 아닐 수 있음. 
# 만약 아니라면, 후입선출 원리로 수열을 표현할 수 없다.
# 따라서 No를 출력하고 문제를 종료한다.
# 만약 현재 수열 값이면 그대로 조건문을 빠져나온다.

# 논점
# 1번째 줄에서 수열의 갯수를 입력받고, 2번째 줄에서는 n개의 수를 임의로 입력받음
# 이때 오름차순 정렬이라는게 keypoint
# 사용자한테 입력받은 수열을 오름차순으로 출력해야함.
# 출력하기 위해 pop이 사용되는데 pop은 단방향에서 이루어지기 때문
# 2번째 예시에서 안되는 이유는 1, 2가 pop된 이후 3이 pop해야하는데 4가 막고 있어서 못함!


# 슈도코드
# n 수열 개수, List 수열 리스트
# List 수열 리스트를 임의의 값으로 채우기

# for n만큼 반복:
#     if 현재 수열 > 오름차순 자연수:
#         while 현재 수열값 >= 오름차순 자연수:
#             append()
#             오름차순 자연수 +=1
#             (+)저장
#         pop()
#         (-)저장
#     else    현재 수열 < 오름차순 자연수:
#         pop()
#         if 스택 pop 결괏값 > 수열 수:
#             No 출력
#         else:
#             (-)저장

# if No를 출력하지 않았다면:
#     저장된 값 출력


# Solution Code
n = int(input())
List = [0]*n

for i in range(n):
    List[i] = int(input())
    
stack = [] # 스택
num = 1 # 현재 push할 숫자
res = True # 수열이 생성 가능 한지 판단
ans = "" # 연산 기록

for i in range(n):
    ai = List[i]
    if ai >= num:
        while ai >= num:
            stack.append(num)
            num += 1
            ans += "+\n"
        stack.pop()
        ans += "-\n"
    else:
        top = stack.pop()
        if top > ai:
            print("NO")
            res = False
            break
        else:
            ans += "-\n"

if res:
    print(ans)

# ai = 현재 수열 값
# num = push할 숫자

# if문은 case1일때 동작
# 그대로 num을 push(append)하고, num을 증가시키고, +출력
# 이후 stack에서 해당 값을 pop한 후 -출력

# else문은 case2일때 동작
# top은 stack에서 pop한 값, 이게 현재 수열 값보다 크면, 수열 생성 불가
# 그게 아니라면, pop했으므로 -출력