← 返回题目列表

AtCoder · arc147_b

B. 交换排序

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

给你一个排列 P=(P_1,P_2,\ldots,P_N) of (1,2,\ldots,N).

您可以按任意顺序重复以下两种操作,使 P 按升序排序。

  • 操作 A: 选择一个整数 i 这样 1 \leq i \leq N-1,并交换 P_i 和 P_{i+1}.

  • 操作 B: 选择一个整数 i 这样 1 \leq i \leq N-2,并交换 P_i 和 P_{i+2}.

查找具有以下属性的操作序列:

  • 操作次数 A 是可能的最小值。

  • 操作总数不大于 10^5.

在这个问题的约束下,我们可以证明解总是存在。

约束

  • 2 \leq N \leq 400
  • 1 \leq P_i \leq N \,(1 \leq i \leq N)
  • P_i \neq P_j \,(1 \leq i < j \leq N)
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
P_1 P_2 \ldots P_N

输出

让 S 是您答案中的操作数。 打印 S+1 行。

第一行应包含 S.

的 (s+1)-th (1 \leq s \leq S)行应包含以下内容:

  • A i 如果 s- 第一个操作是操作 A,并且在此操作中选择的整数是 i.

  • B i 如果 s- 第一个操作是操作 B,并且在此操作中选择的整数是 i.

如果有多个满足条件的解,则打印其中任意一个。


示例输入 1

4
3 2 4 1

示例输出 1

4
A 3
B 1
B 2
B 2

在此示例输出中, P 变化如下: (3,2,4,1) \rightarrow (3,2,1,4) \rightarrow (1,2,3,4) \rightarrow (1,4,3,2) \rightarrow (1,2,3,4).

请注意,您不必最小化操作总数。


示例输入 2

3
1 2 3

示例输出 2

0

示例输入 3

6
2 1 4 3 6 5

示例输出 3

3
A 1
A 3
A 5