# [Solution] Two Trains solution codechef

Two Trains solution codechef – There are 2 trains A and B and N stations in a line from 1 to N in order. There is also an array P of length N-1 such that P_i (1\le i \lt N) denotes the amount of time any train takes to go from the i-th station to the (i+1)-th station.

## [Solution] Two Trains solution codechef

Initially, both trains are at station 1. Train A departs from station 1 and stops directly at station N. For safety purposes, it is maintained that train B cannot depart from station i unless train A has already reached station (i+1) (1 \le i \lt N).

Find the minimum time after which train B reaches station N, once train A departs from station 1.

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains an integer N, denoting number of stations.
• The next line contains N-1 space-separated integers, P_1,P_2,\ldots ,P_{N-1}.

### Output Format

For each test case, output on a new line the minimum time after which train B reaches station N.

## [Solution] Two Trains solution codechef

• 1 \leq T \leq 100
• 2 \leq N \leq 10^5
• 1 \leq P_i \leq 10^3
• The sum of N over all test cases won’t exceed 10^5.

### Sample 1:

Input

Output

3
2
4
3
3 5
4
5 2 6

8
13
19


## Two Trains solution codechef Explanation:

Test case 1: A reaches station 2 at t=4 and at this time B departs from station 1 and reaches station 2 at t=4+4=8.

Test case 1: Following is the timeline of two trains-

• At t=3A reaches station 2 and B departs from station 1.
• At t=6B reaches station 2 but A has not yet reached station 3, so train B will wait at station 2.
• At t=8A reaches station 3 and B departs from station 2.
• At t=8+5=13, train B reaches station 3.