Stack Sequence

A stack is a LIFO (Last In, First Out) data structure: the last value pushed into it is the first value popped from it. Values are handled with two operations, push and pop.

Suppose the numbers from 1 to n may be pushed only in increasing order. By choosing when to push and pop, some sequences can be produced. Given a target sequence, determine whether it can be produced with the stack, and if it can, output the required sequence of operations.

The first line contains an integer n. (1 <= n <= 100,000)

Each of the next n lines contains one element of the target sequence in order. Every element is an integer from 1 to n, and no integer appears more than once.

If the target sequence can be produced, output one operation per line. Print + for a push operation and - for a pop operation.

If the sequence cannot be produced, print NO.

For the numbers from 1 to 8, performing push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop produces [4, 3, 6, 8, 7, 5, 2, 1].