#W1019. 诡异降临

诡异降临

题目背景

诡异降临,整座城市被一股不可名状的力量笼罩。你睁开眼,发现自己被困在了一栋 NN 层高的废弃大楼电梯内。 大楼的规则已经扭曲:每一层楼的墙壁上都刻着一个血红的数字 kik_i,这代表了电梯在该层仅有的两种移动方式。只有在规定的时间内找到前往“安全点”的路径,才能在这场灾难中幸免于难。

题目描述

大楼共有 NN 层。当你身处第 ii 层时,你只能选择向上移动 kik_i 层(到达 i+kii + k_i 层)或者向下移动 kik_i 层(到达 ikii - k_i 层)。

规则限制:

  1. 移动后的目标层数必须在 11NN 之间(包含 11NN)。
  2. i+ki>Ni + k_i > N,则无法向上移动;若 iki<1i - k_i < 1,则无法向下移动。

给定你当前的初始楼层 AA 和安全点所在的楼层 BB,请计算最少需要经过几次电梯移动才能到达 BB

输入格式

第一行包含三个整数 N,A,BN, A, B1N105,1A,BN1 \le N \le 10^5, 1 \le A, B \le N)。

第二行包含 NN 个整数,依次为 k1,k2,,kNk_1, k_2, \dots, k_N0kiN0 \le k_i \le N)。

输出格式

一个整数,表示到达安全点的最少移动次数。如果无论如何都无法到达,请输出 -1

样例

5 1 5
3 3 1 2 5
3

样例解释

  1. 初始在第 1 层,k1=3k_1 = 3,向上移动至第 4 层(1+3=4)。
  2. 在第 4 层,k4=2k_4 = 2,向下移动至第 2 层(4-2=2)。
  3. 在第 2 层,k2=3k_2 = 3,向上移动至第 5 层(2+3=5),到达安全点。 总计移动 3 次。