#4036. [JSOI2016] 反质数序列

[JSOI2016] 反质数序列

[JSOI2016] 反质数序列

题目描述

对于一个长度为 L2L \ge 2 的序列 X:{x1,x2,...,xL}X:\{x_1,x_2,...,x_L\},如果满足对于任意 1i<jL1 \le i < j \le L,均有 xi+xjx_i+x_j 不为质数,则 JYY 认为序列 XX 是一个「反质数序列」。

JYY 有一个长度为 NN 的序列 A:{a1,a2,...,aN}A:\{a_1,a_2,...,a_N\},他希望从中选出一个包含元素最多的子序列,使得这个子序列是一个反质数序列。

输入格式

输入第一行包含一个正整数 NN

接下来一行包含 NN 个正整数,依次描述 a1,a2,...,aNa_1,a_2,...,a_N

输出格式

输出一行一个整数,表示最长反质数子序列的长度。输入保证存在反质数子序列。

样例 #1

样例输入 #1

6
1 2 2 3 4 10

样例输出 #1

4

提示

对于 10%10\% 的数据,满足 N10N \le 10

对于 40%40\% 的数据,满足 N150N \le 150

对于 80%80\% 的数据,满足 N1000N \le 1000

对于 100%100\% 的数据,满足 2N30002 \le N \le 30001ai1051 \le a_i \le 10^5