Dotcpp  >  编程题库  >  蓝桥杯2024年第十五届省赛真题-传送阵
题目 3244:

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

时间限制: 2s 内存限制: 512MB 提交: 1242 解决: 299

题目描述

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

输入格式

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

输出格式

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

样例输入

5
2 1 5 4 3

样例输出

4

提示

【样例说明】

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

【评测用例规模与约定】

对于 20% 的评测用例,1 ≤ n ≤ 1000 ;对于所有评测用例,1 ≤ n ≤ 106,且 a 是 1 至 n 的一个排列。

标签