Prefixmaxxing — Eolymp

Input

The first line consists of a single integer $t$ ( $1 \leq t \leq 2 \cdot 1 0^{5}$ 1 \le t \le 2 \cdot 10^5) $-$ the number of testcases.

The description of each testcase follows.

The first line of each testcase contains an integer $n$ ( $1 \leq n \leq 2 \cdot 1 0^{5}$ 1 \le n \le 2 \cdot 10^5) $-$ the size of array $a$ .

The next line contains $n$ integers $a_{1}, a_{2}, ..., a_{n}$ a_1 , a_2 , ... , a_n ( $- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ -10^9 \le a_i \le 10^9) $-$ the elements of array $a$ .

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Output

The output consists of $t$ lines, each containing one value (the maximum mog value you can get after performing the described operation exactly once).

Examples

Example 1

Loading

Scoring

Subtask $1$ ( $300$ points): No additional constraints