← 返回题目列表

Codeforces · 432/C

C. Prime 掉期

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

你有一个数组 a[1], a[2], ..., a[n],包含从 1 到 n 的不同整数。您的任务是通过以下操作按升序对该数组进行排序(您可能需要多次应用它):

- 选择两个索引,i和j(1 ≤ i < j ≤ n;(j - i + 1)是素数);
- 交换位置 i 和 j 上的元素;换句话说,您可以应用以下赋值序列:tmp = a[i], a[i] = a[j], a[j] = tmp(tmp是临时变量)。

您不需要最小化所用操作的数量。但是,您需要确保最多有 5n 次操作。

输入

第一行包含整数 n (1 ≤ n ≤ 105)。下一行包含 n 个不同的整数 a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ n)。

输出

在第一行中,打印整数 k (0 ≤ k ≤ 5n) — 使用的操作数。接下来,打印操作。每个运算必须打印为“i j”(1 ≤ i < j ≤ n;(j - i + 1) 是素数)。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

3
3 2 1

输出 #1

1
1 3

输入 #2

2
1 2

输出 #2

0

输入 #3

4
4 2 3 1

输出 #3

3
2 4
1 2
2 4