蓝桥杯2024年第十五届省赛真题-传送阵

小蓝在环球旅行时来到了一座古代遗迹，里面并排放置了 n 个传送阵，进入第 i 个传送阵会被传送到第 ai 个传送阵前，并且可以随时选择退出或者继续进入当前传送阵。小蓝为了探寻传送阵中的宝物，需要选择一个传送阵进入，然后连续进入之后的传送阵。小蓝希望尽可能多地进入传送门以便搜索宝物，同时他可以使用一次魔法，从某个传送阵 j 走到相邻的（第 j − 1 或第 j + 1 个）传送阵，请问小蓝最多能到达多少个不同的传送阵？一个传送阵可多次进入，但在计算答案时只算一个。

输入的第一行包含一个正整数 n 。第二行包含 n 个正整数 a1, a2, · · · , an ，相邻整数之间使用一个空格分隔。

输出一行包含一个整数表示答案。

【样例说明】

小蓝的路径可以是：1 → 2 → 3 → 5 。其中 2 → 3 使用魔法。

【评测用例规模与约定】

对于 20% 的评测用例，1 ≤ n ≤ 1000 ；对于所有评测用例，1 ≤ n ≤ 10⁶，且 a 是 1 至 n 的一个排列。

蓝桥杯