1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
using ll = long long ;
using pii = pair <int,int> ;
using pll = pair<ll,ll> ;
using vi = vector <int> ; 
using vll = vector < ll > ;
using tiii = tuple<int,int,int> ; 
using ld = long double ; 
using vpll = vector < pll > ;

#define int long long
#define cYes {cout<<"YES\n";return;}
#define cNo {cout<<"NO\n";return;}
#define bra(x) "[" << (x) << "] "
#define ndl '\n' ;
#define all(x) (x).begin() , (x).end() 
#define sz(x) (int)(x).size() 
#define nd second 
#define st first
#define vvi vector<vector<int>> 

//#define DEBUG
#ifdef DEBUG 
#define dbg(x) cerr << #x << " = " << x << endl 
#else
#define DEBUG 
#endif

const int INFI = 1e9 + 77 ;

int N ;
const int maxn = 100'007 ;
int arr[maxn] ;
vi primes ; 
vector <bool> sieve(maxn+77) ;
void initialize(){
    for(int i=1;i<=N;++i){
        cin >> arr[i] ;
    }
    
    for(int i=2;i<=N;++i){
        if( sieve[i] == 0 ){
            primes.push_back(i) ;
            int x = i ; 
            while(x<=N){
                sieve[x] = 1 ;
                x+=i ;
            }
        }
    }
    
}

bool solve( int spra ){
    if( spra > N ) return false ;
    vi diff_arr(N+7) ;
    int teraz = 0 ;
    for(int i=1;i<=N;++i){
        teraz += diff_arr[i] ;
        if( teraz > arr[i] ) { return false ; }
        int roz = arr[i] - teraz ;
        teraz = arr[i] ;
        if( spra + i > N+1 and roz != 0 ){
            return false ;
        }
        if( spra + i <=N+1) diff_arr[spra+i] -= roz ;
    }
    return true ;
}

signed main(){
    ios_base::sync_with_stdio(false) ; cin.tie(0) ;
    cin >> N ;
    initialize() ;
    vi good_prime ;
    
    
    int bans = 1 ;
    
    for(auto x : primes ){
        int y = x ;
        while( solve(y) ) {
            int nowy = x ;
            good_prime.push_back(y) ;
            bans = max(bans , y) ;
            y *= x ;
        }
    }
    vector<bool> moze(N+7) ;
    moze[1] = 1 ;
    for(auto x : good_prime ){
        int koniec = (N/x) * x ;
        for(int i=koniec;i>=1;i-=x){
            if( moze[i/x] ){
                moze[i] = 1 ;
            }
        }
    }
    for(int i=N;i>=1;i--){
        if(moze[i] and bans < i ){
            if( solve(i) ){
                cout << i << ndl ;
                return 0 ;
            }
        }
    }
    cout << bans << ndl ;
    
    return 0 ;
}