LCC/Moose '19 Contest 4 J5 - Permutation Recovery

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

Given a string S of length N consisting of < and >, generate a permutation A of the integers [1,N+1] such that if S_i = <, A_i < A_{i+1}, otherwise, A_i > A_{i+1}. If there are multiple solutions, print the lexicographically least.

Input Specification

The first line of input will contain the integer N\ (1 \leq N \leq 10^6), the length of the string. The next line will contain the string S of length N.

Output Specification

On one line, output the lexicographically least permutation A that satisfies the requirements.


Subtask 1 [30%]

N \leq 10^3

Subtask 2 [70%]

No further constraints.

Sample Input


Sample Output

1 2 4 3 5


There are no comments at the moment.