Teleportation Points (APCS 2019-10 Advanced)

2.0s 256M

Positions are \(0..n-1\). Start at \(0\) and reach \(P\). One move first goes from \(u\) to \(v=u-L\) or \(u+R\), then immediately teleports to \(S_v\). Both positions must be in range. This entire action costs one move and triggers exactly one teleport, without chaining. Find the minimum moves.

Input

Read \(n,P,L,R\), then \(S_0\) through \(S_{n-1}\).

Constraints

\(2\le n\le10^6\), \(0\le P<n\), \(1\le L,R\le\lfloor n/2\rfloor\), \(|S_i|\le10^8\), \(S_0=0\), \(S_P=P\).

Output

Print the minimum moves, \(-1\) if unreachable, or \(0\) if already at the target.

Sample Input

5 3 1 2
0 2 4 3 1

Sample Output

2

Source

f166 · 2019-10 APCS.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.