eldenrunes

Tarnished a descoperit o arenă circulară păzită de Malenia, formată din $N$ Grace Stones (pietre ale harului), numerotate de la $1$ la $N$ și dispuse în cerc -- piatra $N$ este urmată de piatra $1$. Fiecare Grace Stone $i$ are o putere magică $P_i$, ce determină distanța exactă pe care Tarnished o parcurge într-o singură săritură de pe acea piatră.

Tarnished se află inițial pe Grace Stone-ul $1$ și dorește să ajungă pe Grace Stone-ul $K$, unde se află un Site of Grace. Fiind pe piatra cu indicele $i$, el sare exact $P_i$ poziții înainte în sensul cercului.

Cerințe

• Pentru $C = 1$, determinați numărul minim de sărituri necesare pentru ca Tarnished să ajungă de pe piatra $1$ pe piatra $K$. Dacă acest lucru este imposibil, afișați $-1$.
• Pentru $C = 2$, Malenia îi oferă lui Tarnished posibilitatea de a schimba puterea magică a unei singure Grace Stone (la orice valoare întreagă între $1$ și $T$, inclusiv). Modificarea este opțională. Care este numărul minim de sărituri necesare pentru a ajunge de pe piatra $1$ pe piatra $K$ în aceste condiții? Dacă nici cu această modificare destinația nu poate fi atinsă, afișați $-1$.

Date de intrare

Fișierul de intrare runes.in conține pe prima linie patru numere naturale $C$, $N$, $K$ și $T$, separate prin câte un spațiu, unde $C$ este cerința care trebuie rezolvată ($1$ sau $2$), $N$ este numărul de Grace Stones, $K$ este indicele pietrei destinație, iar $T$ este puterea magică maximă.

Pe a doua linie se află $N$ numere naturale $P_1, P_2, \ldots, P_N$, separate prin câte un spațiu, reprezentând puterile magice ale celor $N$ Grace Stones.

Date de ieșire

Fișierul de ieșire runes.out va conține pe prima linie un singur număr întreg: răspunsul la cerința $C$ (numărul minim de sărituri, sau $-1$ dacă destinația nu poate fi atinsă).

Restricții și precizări

• $2 \leq K \leq N \leq 100\,000$
• $1 \leq T \leq 9$
• $1 \leq P_i \leq T$, pentru orice $1 \leq i \leq N$
• $C \in \{1, 2\}$

Exemplul 1

runes.in

1 7 2 9
6 2 2 5 3 2 2

runes.out

2

Explicație

($C = 1$): Arena are $N = 7$ Grace Stones dispuse circular, cu puterile $[6, 2, 2, 5, 3, 2, 2]$ și $T = 9$. Tarnished pornește de pe piatra $1$ și vrea să ajungă pe piatra $2$.

De pe piatra $1$ (putere $6$), Tarnished sare exact $6$ poziții înainte și ajunge pe piatra $7$. De pe piatra $7$ (putere $2$), sare exact $2$ poziții înainte, trecând circular prin capătul cercului, și ajunge pe piatra $2$. Drumul optim: $1 \rightarrow 7 \rightarrow 2$, adică $\mathbf{2}$ sărituri.

Exemplul 2

runes.in

2 12 11 9
2 5 5 7 7 3 1 3 5 1 5 8

runes.out

2

Explicație

($C = 2$): Arena are $N = 12$ Grace Stones cu puterile $[2, 5, 5, 7, 7, 3, 1, 3, 5, 1, 5, 8]$ și $T = 9$. Tarnished pornește de pe piatra $1$ și vrea să ajungă pe piatra $11$.

Fără nicio modificare, drumul optim necesită $3$ sărituri: $1 \xrightarrow{+2} 3 \xrightarrow{+5} 8 \xrightarrow{+3} 11$.

Dacă Malenia schimbă puterea pietrei $1$ de la $2$ la $3$, drumul devine $1 \xrightarrow{+3} 4 \xrightarrow{+7} 11$, adică $\mathbf{2}$ sărituri. Se poate verifica că nu există nicio modificare care să permită o singură săritură (distanța de la piatra $1$ la piatra $11$ este $10 > T = 9$).