SPPPSPSS. 代表 Sort Permutation Performing Prefix Sort Plus Suffix Sort（执行前缀排序加后缀排序的排列排序）。
给定一个长度为 $n$ 的排列 $p$。你希望通过最少次数的操作将其按升序排序。在第 $k$ 次操作中，你需要选择长度为 $k$ 的前缀或长度为 $k$ 的后缀，并将其按升序排序。
输入格式
第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示排列的大小。 第二行包含排列 $p_1, p_2, \dots, p_n$。
输出格式
假设将给定排列排序所需的最少操作次数为 $m$。你需要输出一个长度为 $m+1$ 的字符串，最后一个字符应为 “.”，其余字符应为 “P” 或 “S”，分别描述在相应操作中选择排序前缀（“P”）还是后缀（“S”）。
样例
样例输入 1
3 1 2 3
样例输出 1
.
样例输入 2
2 2 1
样例输出 2
SP.
样例输入 3
9 3 2 4 1 5 6 7 9 8
样例输出 3
SSSP.
样例输入 4
10 2 9 5 7 10 6 3 1 8 4
样例输出 4
SPPPSPSS.
说明
以下是第四个样例中排列的变化过程：
| 变换前 | 操作 | 变换后 |
|---|---|---|
| 2 9 5 7 10 6 3 1 8 4 | S : 排序长度为 1 的后缀 | 2 9 5 7 10 6 3 1 8 4 |
| 2 9 5 7 10 6 3 1 8 4 | P : 排序长度为 2 的前缀 | 2 9 5 7 10 6 3 1 8 4 |
| 2 9 5 7 10 6 3 1 8 4 | P : 排序长度为 3 的前缀 | 2 5 9 7 10 6 3 1 8 4 |
| 2 5 9 7 10 6 3 1 8 4 | P : 排序长度为 4 的前缀 | 2 5 7 9 10 6 3 1 8 4 |
| 2 5 7 9 10 6 3 1 8 4 | S : 排序长度为 5 的后缀 | 2 5 7 9 10 1 3 4 6 8 |
| 2 5 7 9 10 1 3 4 6 8 | P : 排序长度为 6 的前缀 | 1 2 5 7 9 10 3 4 6 8 |
| 1 2 5 7 9 10 3 4 6 8 | S : 排序长度为 7 的后缀 | 1 2 5 3 4 6 7 8 9 10 |
| 1 2 5 3 4 6 7 8 9 10 | S : 排序长度为 8 的后缀 | 1 2 3 4 5 6 7 8 9 10 |