Рахунок подорожі зі стрибком#13064

Рахунок подорожі зі стрибком

2 секунди

256 мегабайтів

Вам задано масив $a$ , що складається з $n$ елементів, пронумерованих $1, 2, ..., n$ 1,2,...,n.

Ви вирушаєте в подорож, яка починається з $i = 1$ i = 1 і завершується, коли ви досягаєте $i = n + 1$ i = n+1.

Ви починаєте з рахунком $c = 0$ c = 0, і під час подорожі ви можете виконувати такі дії.

додати $a_{i}$ a_i до рахунку, а потім перейти до індексу $i + 1$ i+1.
вибрати додатне ціле число $d$ , для якого $i + d \leq n + 1$ i+d \le n+1, а потім стрибнути до індексу $i + d$ i+d використайте дерево відрізків, щоб обчислити мінімальну суму підмасиву.

Знайдіть максимальний рахунок, який ви можете отримати, якщо операцію стрибка дозволено виконати не більше одного разу.

Вхідні дані

Перший рядок містить одне ціле число $t$ ( $1 \leq t \leq 1 0^{4}$ 1 \le t \le 10^4) — кількість тестових випадків.

Перший рядок кожного тестового випадку містить одне ціле число $n$ ( $1 \leq n \leq 4 \cdot 1 0^{5}$ 1 \le n \le 4 \cdot 10^5) — довжину масиву $a$ .

Другий рядок кожного тестового випадку містить $n$ цілих чисел $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) — масив $a$ .

Гарантується, що сума $n$ за всіма тестовими випадками не перевищує $4 \cdot 1 0^{5}$ 4 \cdot 10^5.

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — максимальний рахунок, який ви можете отримати.

Приклади

Приклад 1

Примітка

У першому тестовому випадку оптимально додати всі елементи, тому підсумковий рахунок дорівнює $1 + 2 + 3 + 4 + 5 = 15$ 1 + 2 + 3 + 4 + 5 = 15.

У другому тестовому випадку можна зробити так:

$i = 1$ i=1, додати $10$ до рахунку та перейти до $i = 2$ i=2.

$i = 2$ i=2, вибрати $d = 3$ d=3, виконати стрибок до $i = 5$ i = 5 і завершити подорож.

Отже, підсумковий рахунок дорівнює $10$ .

Оцінювання

Підзадача $1$ ( $10$ балів): $0 \leq a_{i}$ 0 \le a_i для всіх $i$ ( $1 \leq i \leq n$ 1 \le i \le n).
Підзадача $2$ ( $10$ балів): $\sum n \leq 20$ \sum n \le 20.
Підзадача $3$ ( $30$ балів): $\sum n \leq 5000$ \sum n \le 5000.
Підзадача $4$ ( $50$ балів): Без додаткових обмежень.