28198번 - SPPPSPSS. 스페셜 저지다국어

SPPPSPSS. stands for Sort Permutation Performing Prefix Sort Plus Suffix Sort.

You are given a permutation $p$ of length $n$. You want to sort it in increasing order using the minimum number of operations. In the $k$-th operation you need to choose either the prefix of length $k$ or the suffix of length $k$, and sort it in increasing order.

The first line contains one integer $n$ ($1 \le n \le 10^6$) --- the size of the permutation.

The second line contains the permutation $p_1, p_2, \ldots, p_n$.

Suppose the minimum number of operations needed to sort the given permutation is equal to $m$. Then you should print a string of length $m+1$, the last character should be ".", and all other characters should be either "P" or "S" describing whether you want to sort prefix ("P") or suffix ("S") in the respective operation.

This is how the permutation will change in the fourth sample: