# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Abhinav Sharma

*Nishank Suresh, Nishant Shah*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1230

# PREREQUISITES:

None

# PROBLEM:

There are two trains A and B, and N stations. A train takes time P_i to go from station i to station (i+1).

Train B can depart from station i only after train A has reached station (i+1). What is the minimum amount of time needed for train B to reach station N?

# EXPLANATION:

Let S = P_1 + P_2 + \ldots + P_{N-1}, i.e, the sum of all the elements of P.

Let M = \max(P_1, P_2, \ldots, P_{N-1}), i.e, the maximum element of P.

Then the answer is just S + M.

## How?

The journey of train B can be broken into two separate parts: time taken by it when travelling from one station to another, and time taken while waiting for train A to reach the next station.

The time taken while travelling is clearly just P_1 + P_2 + \ldots + P_{N-1}, by definition.

Now, let M = \max(P_1, P_2, \ldots, P_{N-1}).

The minimum waiting time is definitely at least M, since while train A crosses the section that needs M time, train B cannot move along that section at all, and hence must wait for a total of \geq M units of time already.

Conversely, suppose train B just waits for M seconds at the very beginning before even starting, and starts moving at the end of the M-th second. It is easy to see that, since M = \max(P_1, P_2, \ldots, P_{N-1}), whenever train B is at station i, train A has already reached station (i+1) (and may have gone even further). So, no more waiting time is needed.

Thus, the minimum waiting time is exactly M, and hence the answer is S + M as claimed.

# TIME COMPLEXITY

\mathcal{O}(N) per test case

# CODE:

## Editorialist's Code (Python)

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print(sum(a) + max(a))
```