B4398 [蓝桥杯青少年组国赛 2025] 第三题

洛谷的试题为民间回忆版，仅保证题意相同。试题呈现形式、样例、数据范围可能存在差异。

给定一个包含 $n$ 个正整数的序列 $A = [a_1, a_2, \dots, a_n]$。 你需要从中找出一个**子序列**，使得该子序列中任意两个不同元素的乘积都是一个**完全平方数**。 你的任务是求出满足条件的**最长**子序列的长度。 **提示：** * **子序列**：从原序列中删除零个或多个元素，其余元素保持原有顺序得到的序列。例如，$[2, 3, 18]$ 是 $[2, 8, 3, 18, 12]$ 的一个子序列。 * **完全平方数**：一个整数，它可以表示为另一个整数的平方。例如，36 是一个完全平方数，因为 $36 = 6^2$。

输入共两行。 第一行包含一个整数 $n$，表示序列的长度。 第二行包含 $n$ 个用空格隔开的正整数 $a_1, a_2, \dots, a_n$，表示序列中的元素。

输出一个整数，表示满足条件的最长子序列的长度。

### 样例解释 我们可以找到一个满足条件的子序列 $[2, 8, 18]$，其长度为 3。 ### 数据范围与约定 对于 100% 的数据，满足 $1 \le n \le 10^5$，$1 \le a_i \le 10^{7}$。