Overview

When Takahashi performs \(N\) piano pieces in order, calculate the total performance time considering the condition that the performance time is halved when the difficulty is higher than the previous piece.

Analysis

In this problem, the performance time for each piece changes depending on “whether its difficulty is higher than the previous piece.” Specifically:

• The first piece unconditionally takes \(D_1\) minutes.
• For each subsequent piece, if \(D_{i-1} < D_i\), the time becomes \(D_i / 2\) (rounded down), otherwise it takes \(D_i\) minutes.

A straightforward approach is to simulate the process by comparing each piece’s difficulty with the previous one and accumulating the time. Since this requires only a single pass, it is very efficient.

If you try to use complex logic such as “processing consecutive increasing subsequences together,” not only does the implementation become harder, but it may also incur unnecessary computational overhead and potentially result in TLE. However, for this problem, simple sequential processing works fast enough.

Algorithm

1. Add the difficulty of the first piece \(D_1\) to total_time (the first piece always takes the normal time).
2. For each piece from the 2nd onward, process as follows:
   • If the current piece’s difficulty \(D_i\) is greater than the previous piece’s difficulty \(D_{i-1}\), add \(D_i / 2\) to total_time.
   • Otherwise, add \(D_i\) as-is to total_time.
3. After processing all pieces, output total_time.

Example

Sample input:

5
10 20 15 30 25

Calculation process: - Piece 1: 10 minutes → Total: 10 - Piece 2: 20 > 10 → halved → 10 minutes → Total: 20 - Piece 3: 15 < 20 → normal → 15 minutes → Total: 35 - Piece 4: 30 > 15 → halved → 15 minutes → Total: 50 - Piece 5: 25 < 30 → normal → 25 minutes → Total: 75

Answer: 75

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(N)\) (for storing the difficulty list)

Implementation Notes

• The first piece must be treated specially and always added at normal time.
• By using integer division (//), floor division is naturally expressed.
• Receiving the input as a list is simple and safe.

## Source Code

```python
N = int(input())
D = list(map(int, input().split()))

total_time = D[0]

for i in range(1, N):
    if D[i-1] < D[i]:
        total_time += D[i] // 2
    else:
        total_time += D[i]

print(total_time)

---

This editorial was generated by qwen3-coder-480b.