Language: C++

#include <bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
const int INF=1e9;
//const int MOD=998244353;
const long long LINF=1e18;
//template
int N,now,T=200001;
map<int,int> ma;
int dpw[11][200001];
std::vector<int> v(T),w(T),dp(T),subma(T);//w[i]はi番目のmapのそれの容量
/*
v[i-1]<v[i]の場合はその分だけ0を付け足せばいい
v[i-1]==V[i]の場合は末尾に1を追加 mになろうとしたら1繰り上げて本人は0になる
v[i-1]>v[i]の場合は削ってから末尾に1を追加

0文字目に入ってきたらout

このままだと1e9個の容量を用意する必要があるので考える
mapで座圧して容量を差で考える
例えばv[i]で6の次に大きい数が9の場合、９のやつが容量pw(3,m)を持つと考える
*/
int pw(int n,int k){
  //if(k<0)return pw(n,k+MOD-1);
  if(k<0)return INF;
  if(k>5)return INF;
  if(n<=10)return dpw[n][k];
  int res=1;
  while(k--){
    res*=n;
    if(res>1000000)return INF;
    if(res<0)return INF;
  }
  return res;
}
int left,right=200000;
bool can(int m){
  dp[0]=0;
  if(1<left)fill(dp.begin()+1,dp.begin()+l,0);
  if(right<subma[j]+1)fill(dp.begin()+right+1,dp.begin()+subma[0]+1,0);
  //fill(dp.begin()+1,dp.begin()+subma[0]+1,0);//for(int i=1;i<=subma[0];i++)dp[i]=0;
  //if(m<=5){cout<<m<<":";for(int j=0;j<=5;j++)cout<<dp[j]<<" ";cout<<endl;}
  left=1,right=subma[0];
  for(int j=1;j<N;j++){
    if(v[j]>v[j-1]){//fill(dp.begin()+subma[j-1]+1,dp.begin()+subma[j]+1,0);//for(int i=subma[j-1]+1;i<=subma[j];i++)dp[i]=0;
      if(subma[j-1]+1<=min(left,subma[j]+1))fill(dp.begin()+subma[j-1]+1,dp.begin()+min(left,subma[j]+1),0);
      if(max(right+1,subma[j-1]+1)<=subma[j]+1)fill(dp.begin()+max(right+1,subma[j-1]+1),dp.begin()+subma[j]+1,0);
      left=min(left,subma[j-1]+1);
      right=max(right,subma[j]);
    }
    else{
      dp[subma[j]]++;
      now=subma[j];
      while(dp[now]==pw(m,w[now])){
        dp[now]=0;
        dp[--now]++;
      }
      if(subma[j]+1<left)fill(dp.begin()+subma[j]+1,dp.begin()+left,0);
      left=subma[j]+1;
    }
    //if(m<=5){cout<<m<<":";for(int j=0;j<=5;j++)cout<<dp[j]<<" ";cout<<endl;}
    if(dp[0])return false;
  }
  return true;
}
//main
signed main(){
  cin>>N;
  for(int i=0;i<N;i++)cin>>v[i];
  bool f=true;for(int i=1;i<N;i++)if(v[i]<=v[i-1])f=false;if(f){cout<<1<<endl;return 0;}
  for(int i=0;i<N;i++)ma[v[i]]=0;
  ma[0]=0;int tmp=-1;int cnt=0;
  for(auto &p:ma){
    if(~tmp)w[cnt]=p.first-tmp;
    tmp=p.first;
    p.second=cnt++;
  }
  for(int i=0;i<N;i++)subma[i]=ma[v[i]];
  w[0]=-1;
  for(int i=2;i<=10;i++){
    dpw[i][0]=1;
    for(int j=1;j<T;j++){
      dpw[i][j]=min(10000000,dpw[i][j-1]*i);
      if(dpw[i][j]==10000000){
        for(int k=j+1;k<T;k++)dpw[i][j]=10000000;
        continue;
      }
    }
  }
  int l=1,r=N+2,m=10;
  if(can(m))r=m;
  else l=m;
  if(l<100&&r>100){
    m=100;
    if(can(m))r=m;
    else l=m;
  }
  while(r-l>1){
    m=(l+r)>>1;
    if(can(m))r=m;
    else l=m;
  }
  cout<<r<<endl;
}


Compiler output:
a.cc: In function 'bool can(int)':
a.cc:39:8: error: reference to 'left' is ambiguous
   39 |   if(1<left)fill(dp.begin()+1,dp.begin()+l,0);
      |        ^~~~
In file included from /usr/include/c++/14/streambuf:43,
                 from /usr/include/c++/14/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/14/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:54,
                 from a.cc:1:
/usr/include/c++/14/bits/ios_base.h:1062:3: note: candidates are: 'std::ios_base& std::left(ios_base&)'
 1062 |   left(ios_base& __base)
      |   ^~~~
a.cc:36:5: note:                 'int left'
   36 | int left,right=200000;
      |     ^~~~
a.cc:39:42: error: 'l' was not declared in this scope
   39 |   if(1<left)fill(dp.begin()+1,dp.begin()+l,0);
      |                                          ^
a.cc:40:6: error: reference to 'right' is ambiguous
   40 |   if(right<subma[j]+1)fill(dp.begin()+right+1,dp.begin()+subma[0]+1,0);
      |      ^~~~~
/usr/include/c++/14/bits/ios_base.h:1070:3: note: candidates are: 'std::ios_base& std::right(ios_base&)'
 1070 |   right(ios_base& __base)
      |   ^~~~~
a.cc:36:10: note:                 'int right'
   36 | int left,right=200000;
      |          ^~~~~
a.cc:40:18: error: 'j' was not declared in this scope
   40 |   if(right<subma[j]+1)fill(dp.begin()+right+1,dp.begin()+subma[0]+1,0);
      |                  ^
a.cc:40:39: error: reference to 'right' is ambiguous
   40 |   if(right<subma[j]+1)fill(dp.begin()+right+1,dp.begin()+subma[0]+1,0);
      |                                       ^~~~~
/usr/include/c++/14/bits/ios_base.h:1070:3: note: candidates are: 'std::ios_base& std::right(ios_base&)'
 1070 |   right(ios_base& __base)
      |   ^~~~~
a.cc:36:10: note:                 'int right'
   36 | int left,right=200000;
      |          ^~~~~
a.cc:43:3: error: reference to 'left' is ambiguous
   43 |   left=1,right=subma[0];
      |   ^~~~
/usr/include/c++/14/bits/ios_base.h:1062:3: note: candidates are: 'std::ios_base& std::left(ios_base&)'
 1062 |   left(ios_base& __base)
      |   ^~~~
a.cc:36:5: note:                 'int left'
   36 | int left,right=200000;
      |     ^~~~
a.cc:43:10: error: reference to 'right' is ambiguous
   43 |   left=1,right=subma[0];
      |          ^~~~~
/usr/include/c++/14/bits/ios_base.h:1070:3: note: candidates are: 'std::ios_base& std::right(ios_base&)'
 1070 |   right(ios_base& __base)
      |   ^~~~~
a.cc:36:10: note:                 'int right'
   36 | int left,right=200000;
      |          ^~~~~
a.cc:46:28: error: reference to 'left' is ambiguous
   46 |       if(subma[j-1]+1<=min(left,subma[j]+1))fill(dp.begin()+subma[j-1]+1,dp.begin()+min(left,subma[j]+1),0);
      |                            ^~~~
/usr/include/c++/14/bits/ios_base.h:1062:3: note: candidates are: 'std::ios_base& std::left(ios_base&)'
 1062 |   left(ios_base& __base)
      |   ^~~~
a.cc:36:5: note:                 'int left'
   36 | int left,right=200000;
      |     ^~~~
a.cc:46:89: error: reference to 'left' is ambiguous
   46 |       if(subma[j-1]+1<=min(left,subma[j]+1))fill(dp.begin()+subma[j-1]+1,dp.begin()+min(left,subma[j]+1),0);
      |                                                                                         ^~~~
/usr/include/c++/14/bits/ios_base.h:1062:3: note: candidates are: 'std::ios_base& std::left(ios_base&)'
 1062 |   left(ios_base& __base)
      |   ^~~~
a.cc:36:5: note:                 'int left'
   36 | int left,right=200000;
      |     ^~~~
a.cc:47:14: error: reference to 'right' is ambiguous
   47 |       if(max(right+1,subma[j-1]+1)<=subma[j]+1)fill(dp.begin()+max(right+1,subma[j-1]+1),dp.begin()+subma[j]+1,0);
      |              ^~~~~
/usr/include/c++/14/bits/ios_base.h:1070:3: note: candidates are: 'std::ios_base& std::right(ios_base&)'
 1070 |   right(ios_base& __base)
      |   ^~~~~
a.cc:36:10: note:                 'int right'
   36 | int left,right=200000;
      |          ^~~~~
a.cc:47:68: error: reference to 'right' is ambiguous
   47 |       if(max(right+1,subma[j-1]+1)<=subma[j]+1)fill(dp.begin()+max(right+1,subma[j-1]+1),dp.begin()+subma[j]+1,0);
      |                                                                    ^~~~~
/usr/include/c++/14/bits/ios_base.h:1070:3: note: candidates are: 'std::ios_base& std::right(ios_base&)'
 1070 |   right(ios_base& __base)
      |   ^~~~~
a.cc:36:10: note:                 'int right'
   36 | int left,right=200000;
      |          ^~~~~
a.cc:48:7: error: reference to 'left' is ambiguous
   48 |       left=min(left,subma[j-1]+1);
      |       ^~~~
/usr/include/c++/14/bits/ios_base.h:1062:3: note: candidates are: 'std::ios_base& std::left(ios_base&)'
 1062 |   left(ios_base& __base)
      |   ^~~~
a.cc:36:5: note:                 'int left'
   36 | int left,right=200000;
      |     ^~~~
a.cc:48:16: error: reference to 'left' is ambiguous
   48 |       left=min(left,subma[j-1]+1);
      |                ^~~~
/usr/include/c++/14/bits/ios_base.h:1062:3: note: candidates are: 'std::ios_base& std::left(ios_base&)'
 1062 |   left(ios_base& __base)
      |   ^~~~
a.cc:36:5: note:                 'int left'
   36 | int left,right=200000;
      |     ^~~~
a.cc:49:7: error: reference to 'right' is ambiguous
   49 |       right=max(right,subma[j]);
      |       ^~~~~
/usr/include/c++/14/bits/ios_base.h:1070:3: note: candidates are: 'std::ios_base& std::right(ios_base&)'
 1070 |   right(ios_base& __base)
      |   ^~~~~
a.cc:36:10: note:                 'int right'
   36 | int left,right=200000;
      |          ^~~~~
a.cc:49:17: error: reference to 'right' is ambiguous
   49 |       right=max(right,subma[j]);
      |                 ^~~~~
/usr/include/c++/14/bits/ios_base.h:1070:3: note: candidates are: 'std::ios_base& std::right(ios_base&)'
 1070 |   right(ios_base& __base)
      |   ^~~~~
a.cc:36:10: note:                 'int right'
   36 | int left,right=200000;
      |          ^~~~~
a.cc:58:21: error: reference to 'left' is ambiguous
   58 |       if(subma[j]+1<left)fill(dp.begin()+subma[j]+1,dp.begin()+left,0);
      |                     ^~~~
/usr/include/c++/14/bits/ios_base.h:1062:3: note: candidates are: 'std::ios_base& std::left(ios_base&)'
 1062 |   left(ios_base& __base)
      |   ^~~~
a.cc:36:5: note:                 'int left'
   36 | int left,right=200000;
      |     ^~~~
a.cc:58:64: error: reference to 'left' is ambiguous
   58 |       if(subma[j]+1<left)fill(dp.begin()+subma[j]+1,dp.begin()+left,0);
      |                                                                ^~~~
/usr/include/c++/14/bits/ios_base.h:1062:3: note: candidates are: 'std::ios_base& std::left(ios_base&)'
 1062 |   left(ios_base& __base)
      |   ^~~~
a.cc:36:5: note:                 'int left'
   36 | int left,right=200000;
      |     ^~~~
a.cc:59:7: error: reference to 'left' is ambiguous
   59 |       left=subma[j]+1;
      |       ^~~~
/usr/include/c++/14/bits/ios_base.h:1062:3: note: candidates are: 'std::ios_base& std::left(ios_base&)'
 1062 |   left(ios_base& __base)
      |   ^~~~
a.cc:36:5: note:                 'int left'
   36 | int left,right=200000;
      |     ^~~~