#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
int vis[ 100000 ] ;
int st[ 100000 ] ;
int sts;
class Solution{
public :
bool canReach( vector< int > & A, int s) {
int i;
int j;
int N = A.size ( ) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
vis[ i] = 0 ;
}
sts = 0 ;
vis[ s] = 1 ;
st[ sts++ ] = s;
while ( sts) {
int d;
i = st[ -- sts] ;
if ( A[ i] == 0 ) {
return true ;
}
for ( d= ( 0 ) ; d< ( 2 ) ; d++ ) {
if ( d) {
j = i + A[ i] ;
}
else {
j = i - A[ i] ;
}
if ( j < 0 || j >= N) {
continue ;
}
if ( vis[ j] == 0 ) {
vis[ j] = 1 ;
st[ sts++ ] = j;
}
}
}
return false ;
}
}
;
// cLay varsion 20200214-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int vis[1d5], st[1d5], sts;
//
// class Solution {
// public:
// bool canReach(vector<int>& A, int s) {
// int i, j, N = A.size();
// rep(i,N) vis[i] = 0;
// sts = 0;
// vis[s] = 1;
// st[sts++] = s;
// while(sts){
// i = st[--sts];
// if(A[i]==0) return true;
// rep(d,2){
// j = i if[d, +, -] A[i];
// if(j < 0 || j >= N) continue;
// if(vis[j]==0) vis[j] = 1, st[sts++] = j;
// }
// }
// return false;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbWFpbiBkdW1teV9tYWluCmludCBtYWluKCl7CiAgcmV0dXJuIDA7Cn0KI3VuZGVmIG1haW4KaW50IHZpc1sxMDAwMDBdOwppbnQgc3RbMTAwMDAwXTsKaW50IHN0czsKY2xhc3MgU29sdXRpb257CiAgcHVibGljOgogIGJvb2wgY2FuUmVhY2godmVjdG9yPGludD4mIEEsIGludCBzKXsKICAgIGludCBpOwogICAgaW50IGo7CiAgICBpbnQgTiA9IEEuc2l6ZSgpOwogICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgIHZpc1tpXSA9IDA7CiAgICB9CiAgICBzdHMgPSAwOwogICAgdmlzW3NdID0gMTsKICAgIHN0W3N0cysrXSA9IHM7CiAgICB3aGlsZShzdHMpewogICAgICBpbnQgZDsKICAgICAgaSA9IHN0Wy0tc3RzXTsKICAgICAgaWYoQVtpXT09MCl7CiAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgIH0KICAgICAgZm9yKGQ9KDApO2Q8KDIpO2QrKyl7CiAgICAgICAgaWYoZCl7CiAgICAgICAgICBqID0gaSArQVtpXTsKICAgICAgICB9CiAgICAgICAgZWxzZXsKICAgICAgICAgIGogPSBpIC1BW2ldOwogICAgICAgIH0KICAgICAgICBpZihqIDwgMCB8fCBqID49IE4pewogICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIGlmKHZpc1tqXT09MCl7CiAgICAgICAgICB2aXNbal0gPSAxOwogICAgICAgICAgc3Rbc3RzKytdID0gajsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIHJldHVybiBmYWxzZTsKICB9Cn0KOwovLyBjTGF5IHZhcnNpb24gMjAyMDAyMTQtMQoKLy8gLS0tIG9yaWdpbmFsIGNvZGUgLS0tCi8vICNkZWZpbmUgbWFpbiBkdW1teV9tYWluCi8vIHt9Ci8vICN1bmRlZiBtYWluCi8vIAovLyBpbnQgdmlzWzFkNV0sIHN0WzFkNV0sIHN0czsKLy8gCi8vIGNsYXNzIFNvbHV0aW9uIHsKLy8gcHVibGljOgovLyAgIGJvb2wgY2FuUmVhY2godmVjdG9yPGludD4mIEEsIGludCBzKSB7Ci8vICAgICBpbnQgaSwgaiwgTiA9IEEuc2l6ZSgpOwovLyAgICAgcmVwKGksTikgdmlzW2ldID0gMDsKLy8gICAgIHN0cyA9IDA7Ci8vICAgICB2aXNbc10gPSAxOwovLyAgICAgc3Rbc3RzKytdID0gczsKLy8gICAgIHdoaWxlKHN0cyl7Ci8vICAgICAgIGkgPSBzdFstLXN0c107Ci8vICAgICAgIGlmKEFbaV09PTApIHJldHVybiB0cnVlOwovLyAgICAgICByZXAoZCwyKXsKLy8gICAgICAgICBqID0gaSBpZltkLCArLCAtXSBBW2ldOwovLyAgICAgICAgIGlmKGogPCAwIHx8IGogPj0gTikgY29udGludWU7Ci8vICAgICAgICAgaWYodmlzW2pdPT0wKSB2aXNbal0gPSAxLCBzdFtzdHMrK10gPSBqOwovLyAgICAgICB9Ci8vICAgICB9Ci8vICAgICByZXR1cm4gZmFsc2U7Ci8vICAgfQovLyB9Owo=