K. Kyuu Sort
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Osu!

Cindy is helping manage a mixed martial arts tournament that is being hosted at her school. Now that the tournament is over, it's time to get all the competitors lined up for a ceremonial photo...

The tournament included $$$n$$$ martial artists from a variety of disciplines and backgrounds. Cindy's analytics team used an assortment of machine learning techniques in order to assign each competitor a distinct power ranking, an integer from $$$1$$$ to $$$n$$$ that describes their martial arts skill relative to the other martial artists. In this system, $$$1$$$ is the lowest ranking and $$$n$$$ is the highest ranking.

After all, if there's anything that Cindy learned from YouTube, it's that people love power rankings.

These $$$n$$$ martial artists then arranged themselves in a queue, in preparation for the final photo. We can describe their initial ordering by using a permutation $$$p_1, p_2, p_3, \dots, p_n$$$, where $$$p_1$$$ is the ranking of the person currently at the front of the queue, and $$$p_n$$$ is the ranking of the person currently at the back.

However, Cindy believes that she'll get the perfect thumbnail if this queue is sorted in ascending order. That is to say, each competitor must have a higher ranking than everyone in front of them in the queue.

To make sure things don't get too rowdy, Cindy only has the following two possible operations at her disposal.

  • S to swap the positions of the two front-most people in the queue.
  • P to tell the person at the front of the queue to move to the very back; then, everyone adjusts. In other words, we "pop" off the person currently at the front of the queue, then "push" them to the back of the queue.
Cindy has a lot of things on her plate today, though, so do you think you could help her out with this task?
Input

The first line of input contains a single integer $$$n$$$.

The second line of input contains the $$$n$$$ integers $$$p_1, p_2, p_3, \dots, p_n$$$.

$$$$$$\begin{align*}

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{33} & 3 \leq n \leq 5 \\ \hline 2 & \mathbf{33} & 3 \leq n \leq 8 \\ \hline 3 & \mathbf{17} & 3 \leq n \leq 50 \\ \hline 4 & \mathbf{17} & 3 \leq n \leq 250 \\ \hline \end{array}\\

\end{align*}$$$$$$

Output

Output a single string consisting only of the letters S and P, encoding the commands that you would like to give, in order.

If you would like to output the empty string (meaning no operations will be done), output empty instead.

Your solution will be accepted if this string has no more than $$$10^5$$$ characters. We can show that a solution always exists within these bounds. Note that you do not have to minimize the number of operations.

Examples
Input
5
4 3 1 5 2
Output
SPPSP
Input
5
1 2 3 4 5
Output
empty