Overview

We sum up the stamina consumed each time we climb a step. However, only when “the current step height is strictly greater than the previous step height” does the stamina consumption for that step become \(2\) times, so we check this condition in order and compute the total.

Analysis

The key point is that the stamina consumed at step \(i\) is determined “solely by the comparison between \(A_i\) and \(A_{i-1}\).” In other words, there is no need to look at the entire sequence and perform complex optimization — we can determine everything by scanning from left to right.

• Normally, \(A_i\) stamina is consumed
• However, only when \(A_i > A_{i-1}\), \(2A_i\) stamina is consumed
• For the 1st step, there is no previous step to compare with, so it is always \(A_1\)

For example, when \(A = [3, 2, 5, 5]\): - Step 1: \(3\) - Step 2: \(2\) (\(2 \le 3\)) - Step 3: \(10\) (\(5 > 2\), so doubled) - Step 4: \(5\) (\(5 \not> 5\)) The total is \(3+2+10+5=20\).

There is no need to separately count things like “the number of surprises” or use unnecessary data structures. It is sufficient to determine the value to add at each step on the spot and accumulate it. This easily fits within the time limit even for \(N \le 2\times 10^5\).

Algorithm

1. Initialize total with \(A_1\) (the 1st step always has normal consumption).
2. Process each \(i=2..N\) in order (or \(i=1..N-1\) if 0-indexed).
   • If \(A_i > A_{i-1}\), then total += 2*A_i
   • Otherwise, total += A_i
3. Output total.

Complexity

• Time complexity: \(O(N)\) (just one comparison and addition per step)
• Space complexity: \(O(1)\) (constant extra space excluding the input array)

Implementation Notes

• Since the condition is “strictly greater,” the check is \(A_i > A_{i-1}\) (note that the case \(=\) does not result in doubling).

• The total can be as large as approximately \(2 \times 10^9 \times 2 \times 10^5 = 4 \times 10^{14}\), but Python’s int has arbitrary precision, so there is no issue.

• Since the input can be large, using sys.stdin.readline is recommended for safety.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    A = list(map(int, input().split()))
    total = A[0]
    for i in range(1, N):
        if A[i] > A[i - 1]:
            total += 2 * A[i]
        else:
            total += A[i]
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.