\(X=\max(A)\) とすれば明らかに全ての柱を破壊することができます。

衝撃 \(X\) を与えたとき、各柱が受けるダメージは \(X\) か \(X+1\) のどちらかです。よって、全ての柱を破壊するには \(\max(A)-1\) 以上の衝撃を与える必要があります。

以上より、全ての柱を破壊することができる \(X\) の最小値は \(\max(A)-1\) か \(\max(A)\) かのどちらかであるため、\(X=\max(A)-1\) のケースをシミュレーションし、全ての柱を破壊することができれば \(\max(A)-1\) 、できなければ \(\max(A)\) が答えとなります。

なお、実際にはシミュレーションすることなく、\(A_1=\max(A)\) かどうかのみで判定できます。

いずれの場合も計算量は \(O(N)\) です。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i=0; i<n; i++) cin >> a[i];

  int M = *max_element(a.begin(), a.end());
  if(a[0] == M){
    cout << M << endl;
  }else{
    cout << M - 1 << endl;
  }
}

実装例 (Python)

N = int(input())
A = list(map(int, input().split()))

M = max(A)
if A[0] == M:
  print(M)
else:
  print(M - 1)