징검다리의 징검다리

$N$개의 호수가 일렬로 늘어서 있다. 각 호수는 왼쪽에서부터 $1$번에서 $N$번까지 번호가 매겨져 있으며, 각 호수에는 돌들이 원형으로 배치되어 있다. $i$번째 호수에는 징검다리를 이루는 돌이 $A_i$개 있으며, 각 돌에는 $1$번부터 $A_i$번까지 번호가 매겨져 있다.

용모는 $S$번째 호수의 $1$번 돌 위에 서 있으며, 다음과 같은 규칙으로 이동한다.

• 현재 $j$번 돌 위에 있다면 같은 호수의 $j+1$번 돌로 이동한다. 단, 현재 $A_i$번 돌 위에 있다면 $1$번 돌로 이동한다.
• 현재 $j$번 돌 위에 있다면 같은 호수의 $j-1$번 돌로 이동한다. 단, 현재 $1$번 돌 위에 있다면 $A_i$번 돌로 이동한다.
• 현재 $i$번째 호수의 돌 위에 있다면 $i-1$번 또는 $i+1$번 호수의 임의의 돌로 이동한다. 단, $i-1$번 호수 또는 $i+1$번 호수가 존재하지 않는다면 해당 방향으로는 이동할 수 없다.
• 한번 밟은 돌은 다시 밟을 수 없다.

용모가 $E$번째 호수의 임의의 돌에 도착할 때까지, 시작 돌과 끝 돌을 포함하여 정확히 $K$개의 돌을 밟을 수 있는지 판단하는 프로그램을 작성하시오.

첫 번째 줄에 호수의 개수를 나타내는 정수 $N$과 시작 호수와 끝 호수의 번호를 나타내는 정수 $S,E$가 주어진다.

두 번째 줄에 각 호수의 징검다리를 이루는 돌의 개수 $A_1,A_2,\cdots,A_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 용모가 밟아야 하는 서로 다른 돌의 개수 $K$가 주어진다.

용모가 정확히 $K$개의 돌을 밟은 후 $E$번째 호수의 임의의 돌에 도착할 수 있으면 1, 그렇지 않으면 0을 출력한다.

• $2\le N\le 200\, 000$
• $1\le S,E\le N$, $S\neq E$
• $1\le A_i\le 1\, 000$
• $2\le K\le 10^9$