#P18656. SPPPSPSS.
SPPPSPSS.
SPPPSPSS.
SPPPSPSS. 是 Sort Permutation Performing Prefix Sort Plus Suffix Sort 的缩写。
给定一个长度为 的排列 ,请用最少的操作次数把它按递增顺序排好。
在第 次操作中,必须选择下面一种操作:
- 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.
样例说明
下面是原 PDF 中第四个样例的完整操作过程表。Before、Operation、After 分别表示操作前、执行的操作、操作后;表中下划线标出被排序的前缀或后缀。

导入时须把同目录的original_sample4_table.png上传为题面附件,保留上述Hydro附件引用。