← 返回题目列表

AtCoder · arc080_d

F. 总理翻转

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

分数: 1200 点

问题陈述

有无限张牌,编号为 1, 2, 3, ... 最初,卡片 x_1, x_2, ..., x_N 面朝上,其他面朝下。

Snuke可以重复执行以下操作:

  • 选择一个素数 p 大于或等于 3。然后,选择 p 连续的牌并将其全部翻转。

Snuke 的目标是让所有牌面朝下。 找出实现目标所需的最少操作次数。

约束

  • 1 ≤ N ≤ 100
  • 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^7

输入

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

N
x_1 x_2 ... x_N

输出

打印实现目标所需的最少操作数。


示例输入 1

2
4 5

示例输出 1

2

以下是通过两次操作实现目标的一种方法:

  • 选择 p = 5 和翻转卡 1, 2, 3, 4 和 5.
  • 选择 p = 3 和翻转卡 1, 2 和 3.

示例输入 2

9
1 2 3 4 5 6 7 8 9

示例输出 2

3

以下是通过三个操作实现目标的一种方法:

  • 选择 p = 3 和翻转卡 1, 2 和 3.
  • 选择 p = 3 和翻转卡 4, 5 和 6.
  • 选择 p = 3 和翻转卡 7, 8 和 9.

示例输入 3

2
1 10000000

示例输出 3

4