#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
void * wmem;
char memarr[ 96000000 ] ;
template < class T> inline void walloc1d( T ** arr, int x, void ** mem = & wmem) {
static int skip[ 16 ] = { 0 , 15 , 14 , 13 , 12 , 11 , 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 } ;
( * mem) = ( void * ) ( ( ( char * ) ( * mem) ) + skip[ ( ( unsigned long long ) ( * mem) ) & 15 ] ) ;
( * arr) = ( T* ) ( * mem) ;
( * mem) = ( ( * arr) + x) ;
}
template < class T1> void sortA_L( int N, T1 a[ ] , void * mem = wmem) {
sort( a, a+ N) ;
}
template < class T1, class T2> void sortA_L( int N, T1 a[ ] , T2 b[ ] , void * mem = wmem) {
int i;
pair< T1, T2> * arr;
walloc1d( & arr, N, & mem) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
arr[ i] .first = a[ i] ;
arr[ i] .second = b[ i] ;
}
sort( arr, arr+ N) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
a[ i] = arr[ i] .first ;
b[ i] = arr[ i] .second ;
}
}
template < class S, class T> inline S chmax( S & a, T b) {
if ( a< b) {
a= b;
}
return a;
}
#define main dummy_main
int main( ) {
wmem = memarr;
return 0 ;
}
#undef main
int x[ 100000 ] ;
int y[ 100000 ] ;
class Solution{
public :
int minTaps( int n, vector< int > & ranges) {
dummy_main( ) ;
int res = 0 ;
int cur = 0 ;
int i;
int mx;
n++ ;
for ( i= ( 0 ) ; i< ( n) ; i++ ) {
x[ i] = i - ranges[ i] ;
}
for ( i= ( 0 ) ; i< ( n) ; i++ ) {
y[ i] = i + ranges[ i] ;
}
sortA_L( n,x,y) ;
i = 0 ;
while ( cur < n- 1 ) {
mx = - 1 ;
while ( i < n && x[ i] <= cur) {
chmax( mx, y[ i++ ] ) ;
}
if ( mx== - 1 ) {
return - 1 ;
}
res++ ;
cur = mx;
}
return res;
}
}
;
// cLay varsion 20200119-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// int x[1d5], y[1d5];
//
// class Solution {
// public:
// int minTaps(int n, vector<int>& ranges) {
// dummy_main();
// int res = 0, cur = 0, i, mx;
// n++;
// rep(i,n) x[i] = i - ranges[i];
// rep(i,n) y[i] = i + ranges[i];
// sortA(n,x,y);
//
// i = 0;
// while(cur < n-1){
// mx = -1;
// while(i < n && x[i] <= cur) mx >?= y[i++];
// if(mx==-1) return -1;
// res++;
// cur = mx;
// }
//
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnZvaWQgKndtZW07CmNoYXIgbWVtYXJyWzk2MDAwMDAwXTsKdGVtcGxhdGU8Y2xhc3MgVD4gaW5saW5lIHZvaWQgd2FsbG9jMWQoVCAqKmFyciwgaW50IHgsIHZvaWQgKiptZW0gPSAmd21lbSl7CiAgc3RhdGljIGludCBza2lwWzE2XSA9IHswLCAxNSwgMTQsIDEzLCAxMiwgMTEsIDEwLCA5LCA4LCA3LCA2LCA1LCA0LCAzLCAyLCAxfTsKICAoKm1lbSkgPSAodm9pZCopKCAoKGNoYXIqKSgqbWVtKSkgKyBza2lwWygodW5zaWduZWQgbG9uZyBsb25nKSgqbWVtKSkgJiAxNV0gKTsKICAoKmFycik9KFQqKSgqbWVtKTsKICAoKm1lbSk9KCgqYXJyKSt4KTsKfQp0ZW1wbGF0ZTxjbGFzcyBUMT4gdm9pZCBzb3J0QV9MKGludCBOLCBUMSBhW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIHNvcnQoYSwgYStOKTsKfQp0ZW1wbGF0ZTxjbGFzcyBUMSwgY2xhc3MgVDI+IHZvaWQgc29ydEFfTChpbnQgTiwgVDEgYVtdLCBUMiBiW10sIHZvaWQgKm1lbSA9IHdtZW0pewogIGludCBpOwogIHBhaXI8VDEsIFQyPiAqYXJyOwogIHdhbGxvYzFkKCZhcnIsIE4sICZtZW0pOwogIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgYXJyW2ldLmZpcnN0ID0gYVtpXTsKICAgIGFycltpXS5zZWNvbmQgPSBiW2ldOwogIH0KICBzb3J0KGFyciwgYXJyK04pOwogIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgYVtpXSA9IGFycltpXS5maXJzdDsKICAgIGJbaV0gPSBhcnJbaV0uc2Vjb25kOwogIH0KfQp0ZW1wbGF0ZTxjbGFzcyBTLCBjbGFzcyBUPiBpbmxpbmUgUyBjaG1heChTICZhLCBUIGIpewogIGlmKGE8Yil7CiAgICBhPWI7CiAgfQogIHJldHVybiBhOwp9CiNkZWZpbmUgbWFpbiBkdW1teV9tYWluCmludCBtYWluKCl7CiAgd21lbSA9IG1lbWFycjsKICByZXR1cm4gMDsKfQojdW5kZWYgbWFpbgppbnQgeFsxMDAwMDBdOwppbnQgeVsxMDAwMDBdOwpjbGFzcyBTb2x1dGlvbnsKICBwdWJsaWM6CiAgaW50IG1pblRhcHMoaW50IG4sIHZlY3RvcjxpbnQ+JiByYW5nZXMpewogICAgZHVtbXlfbWFpbigpOwogICAgaW50IHJlcyA9IDA7CiAgICBpbnQgY3VyID0gMDsKICAgIGludCBpOwogICAgaW50IG14OwogICAgbisrOwogICAgZm9yKGk9KDApO2k8KG4pO2krKyl7CiAgICAgIHhbaV0gPSBpIC0gcmFuZ2VzW2ldOwogICAgfQogICAgZm9yKGk9KDApO2k8KG4pO2krKyl7CiAgICAgIHlbaV0gPSBpICsgcmFuZ2VzW2ldOwogICAgfQogICAgc29ydEFfTChuLHgseSk7CiAgICBpID0gMDsKICAgIHdoaWxlKGN1ciA8IG4tMSl7CiAgICAgIG14ID0gLTE7CiAgICAgIHdoaWxlKGkgPCBuICYmIHhbaV0gPD0gY3VyKXsKICAgICAgICBjaG1heChteCwgeVtpKytdKTsKICAgICAgfQogICAgICBpZihteD09LTEpewogICAgICAgIHJldHVybiAtMTsKICAgICAgfQogICAgICByZXMrKzsKICAgICAgY3VyID0gbXg7CiAgICB9CiAgICByZXR1cm4gcmVzOwogIH0KfQo7Ci8vIGNMYXkgdmFyc2lvbiAyMDIwMDExOS0xCgovLyAtLS0gb3JpZ2luYWwgY29kZSAtLS0KLy8gI2RlZmluZSBtYWluIGR1bW15X21haW4KLy8ge30KLy8gI3VuZGVmIG1haW4KLy8gCi8vIGludCB4WzFkNV0sIHlbMWQ1XTsKLy8gCi8vIGNsYXNzIFNvbHV0aW9uIHsKLy8gcHVibGljOgovLyAgIGludCBtaW5UYXBzKGludCBuLCB2ZWN0b3I8aW50PiYgcmFuZ2VzKSB7Ci8vICAgICBkdW1teV9tYWluKCk7Ci8vICAgICBpbnQgcmVzID0gMCwgY3VyID0gMCwgaSwgbXg7Ci8vICAgICBuKys7Ci8vICAgICByZXAoaSxuKSB4W2ldID0gaSAtIHJhbmdlc1tpXTsKLy8gICAgIHJlcChpLG4pIHlbaV0gPSBpICsgcmFuZ2VzW2ldOwovLyAgICAgc29ydEEobix4LHkpOwovLyAKLy8gICAgIGkgPSAwOwovLyAgICAgd2hpbGUoY3VyIDwgbi0xKXsKLy8gICAgICAgbXggPSAtMTsKLy8gICAgICAgd2hpbGUoaSA8IG4gJiYgeFtpXSA8PSBjdXIpIG14ID4/PSB5W2krK107Ci8vICAgICAgIGlmKG14PT0tMSkgcmV0dXJuIC0xOwovLyAgICAgICByZXMrKzsKLy8gICAgICAgY3VyID0gbXg7Ci8vICAgICB9Ci8vIAovLyAgICAgcmV0dXJuIHJlczsKLy8gICB9Ci8vIH07Cg==