Overview

The essence of this problem is that even when a chain reaction occurs, each pillar receives at most \(1\) additional damage.
Therefore, the first pillar must be toppled with \(X\) alone, and from the second pillar onward, assuming the left neighbor has fallen, it suffices to topple it with \(X+1\). Thus, the answer is

\[ \max \left( A_1,\ \max_{2 \le i \le N}(A_i-1) \right) \]

Analysis

First, let’s organize how each pillar falls.

• All pillars simultaneously receive \(X\) damage at the beginning.
• Then, looking from left to right:
  • If the left neighbor has fallen, that pillar receives an additional \(1\) damage.

The key point here is:

• The first pillar has no left neighbor, so it receives only \(X\) damage.
• The second pillar onward, if the left neighbor has fallen, receives \(X+1\) damage.

Key Insight

When you hear “chain reaction,” you might think “damage gets larger and larger as it propagates to the right,” but that is not the case.
Each pillar receives only \(1\) additional damage from its left neighbor.

In other words, the condition for each pillar is as follows:

• Condition for the 1st pillar to fall: \(A_1 \le X\)
• Condition for the 2nd pillar to fall: the 1st has fallen, and \(A_2 \le X+1\)
• Condition for the 3rd pillar to fall: the 2nd has fallen, and \(A_3 \le X+1\)
• …

Looking at this pattern, as long as the very first pillar falls, everything afterward is determined solely by “whether it can be toppled with \(X+1\).”

---

Necessary Conditions

To topple all pillars, we obviously need:

• For the 1st pillar: \(X \ge A_1\)
• For the 2nd pillar onward: \(X+1 \ge A_i\)
  i.e., \(X \ge A_i-1\)

Therefore, \(X\) must be at least

\[ \max \left( A_1,\ \max_{2 \le i \le N}(A_i-1) \right) \]

---

Is This Truly Sufficient?

Yes, it is sufficient.
If we actually set \(X\) to this value:

• The 1st pillar falls because \(A_1 \le X\)
• Since the 1st pillar has fallen, the 2nd pillar receives \(X+1\) damage
• Moreover, \(A_2 \le X+1\), so it falls
• Then the 3rd pillar falls in the same way
• …
• Repeating this in order, all pillars fall

As we can see, this value is both “necessary” and “sufficient,” so it is exactly the minimum.

---

Concrete Example

For example, if

\[ A = [5, 7, 6, 4] \]

then:

• For the 1st pillar: \(X \ge 5\)
• For the 2nd pillar onward:
  • \(X \ge 7-1=6\)
  • \(X \ge 6-1=5\)
  • \(X \ge 4-1=3\)

So the answer is

\[ \max(5,6,5,3)=6 \]

Indeed, with \(X=6\):

• 1st pillar: receives \(6\) and falls
• 2nd pillar: receives \(6+1=7\) and falls
• 3rd pillar: receives \(7\) and falls
• 4th pillar: receives \(7\) and falls

All pillars fall.

---

Why a Naive Approach Is Unnecessary

A naive approach would be:

• Fix some \(X\) and simulate
• Try this for various values of \(X\)

However, since \(A_i\) can be up to \(10^9\), trying \(X\) from the smallest value upward would be far too slow.

By correctly understanding the chain reaction mechanism, simulation is essentially unnecessary.
The key point is that by simply writing down the condition required for each pillar, the answer can be determined in one shot.

Algorithm

Compute the following:

1. Initialize the answer to \(A_1\)
   (because the 1st pillar must be toppled with \(X\) alone)
2. For the 2nd pillar onward, check \(A_i-1\) and update the answer
3. Output the final maximum value

Written as a formula:

\[ \text{ans} = \max \left( A_1,\ A_2-1,\ A_3-1,\ \dots,\ A_N-1 \right) \]

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

• Only the 1st pillar has a different condition; what’s needed is \(A_1\) itself
• From the 2nd pillar onward, “if the left neighbor falls, \(+1\) damage” applies, so the required condition is \(A_i-1\)
• In Python, arrays are 0-indexed, so in code:
  • A[0] is the 1st pillar
  • Check A[i] - 1 starting from i=1

The submission code is a straightforward implementation of this approach.

Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    
    ans = A[0]
    for i in range(1, N):
        ans = max(ans, A[i] - 1)
    
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.