#P12123. [蓝桥杯 2024 省 B 第二场] 传送阵

[蓝桥杯 2024 省 B 第二场] 传送阵

题目描述

小蓝在环球旅行时来到了一座古代遗迹,里面并排放置了 nn 个传送阵,进入第 ii 个传送阵会被传送到第 aia_i 个传送阵前,并且可以随时选择退出或者继续进入当前传送阵。

小蓝为了探寻传送阵中的宝物,需要选择一个传送阵进入,然后连续进入之后的传送阵。小蓝希望尽可能多地进入传送门以便搜索宝物,同时他可以使用一次魔法,从某个传送阵 jj 走到相邻的(第 j1j - 1 或第 j+1j + 1 个)传送阵,请问小蓝最多能到达多少个不同的传送阵?一个传送阵可多次进入,但在计算答案时只算一个。

输入格式

输入的第一行包含一个正整数 nn

第二行包含 nn 个正整数 a1,a2,,ana_1, a_2, \dots , a_n,相邻整数之间使用一个空格分隔。

输出格式

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

5
2 1 5 4 3
4

提示

样例说明

小蓝的路径可以是:12351 \to 2 \to 3 \to 5。其中 232 \to 3 使用魔法。

评测用例规模与约定

  • 对于 20%20\% 的评测用例,1n10001 \leq n \leq 1000
  • 对于所有评测用例,1n1061 \leq n \leq 10^6,且 aa11nn 的一个排列。