#P18656. SPPPSPSS.

    ID: 17992 传统题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-支配关系阈值二值化前后缀最值一维前缀和计数排序相向双指针增量维护

SPPPSPSS.

SPPPSPSS.

SPPPSPSS. 是 Sort Permutation Performing Prefix Sort Plus Suffix Sort 的缩写。

给定一个长度为 nn 的排列 pp,请用最少的操作次数把它按递增顺序排好。

在第 kk 次操作中,必须选择下面一种操作:

  • P:将排列的前 kk 个元素按递增顺序排序;
  • S:将排列的后 kk 个元素按递增顺序排序。

操作从第 11 次开始编号,排序的长度由当前操作编号确定,不能自行选择。第 11 次操作只排序一个元素。若排列起初已有序,可以不操作。

输入格式

第一行一个整数 nn(1≤n≤1061\le n\le10^6)。

第二行 nn 个整数 p1,p2,…,pnp_1,p_2,\ldots,p_n,构成 11 到 nn 的一个排列。

输出格式

设最少操作次数为 mm。输出一个长度为 m+1m+1 的字符串:最后一个字符为英文句点 .,之前的 mm 个字符只能是 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附件引用。