Description

这是一个交互题。

有一个由 $1$ 到 $n$ 的整数构成的排列 $a[1], a[2], \ldots, a[n]$ 被隐藏了起来。

你的任务是通过比较和交换元素对，将其按升序排序。本题本应很简单，但出题人因为在 G 和 J 题中过于专注于浮点数运算，实现了一个“不精确”的比较器：

• 如果 $\frac{|a[i] - a[j]|}{\max(a[i], a[j])} \leq 0.01$，则返回 $0$；
• 否则，如果 $a[i] < a[j]$，则返回 $-1$；
• 否则，返回 $1$。

你的程序可以使用该比较器对任意两个元素进行比较，也可以交换任意两个元素。每次交换后，系统会告知当前排列是否已经有序。

请在不超过 $300\,000$ 次查询内，将长度不超过 $16\,384$ 的排列排序。

交互说明

首先，你会收到一个整数 $n$，表示排列的长度（$1 \leq n \leq 16\,384$）。然后，你可以输出查询，并读取系统的响应。每次查询后需要刷新输出，并读取一个整数作为响应。

比较查询格式为 $\tt{C\ i\ j}$，交换查询格式为 $\tt{S\ i\ j}$，其中 $i$ 和 $j$ 是元素的下标（$1 \leq i, j \leq n$）。允许 $i = j$。

比较查询的响应为：

• $0$，如果 $a[i]$ “近似等于” $a[j]$；
• $-1$，如果 $a[i] < a[j]$；
• $1$，如果 $a[i] > a[j]$。

交换查询会交换 $a[i]$ 和 $a[j]$ 的值，响应为：

• $1$，如果交换后数组已按升序排列；
• $0$，否则。

一旦收到交换查询的响应为 $1$，你的程序应立即退出。

你的程序至少要进行一次交换查询。例如，如果初始排列已经有序，可以查询 $\tt{S\ 1\ 1}$，收到 $1$ 后退出。

交互器是非自适应的。排列在你第一次查询前就已确定。

Input Format

无。

Output Format

无。

4

-1

-1

1

1

C 1 2

C 2 3

C 3 4

S 3 4

1

1

S 1 1

Hint

由 ChatGPT 4.1 翻译