Zıplamalı Yolculuk Puanı#13064
Size 1,2,...,n şeklinde numaralandırılmış elemandan oluşan bir dizisi veriliyor.
i = 1 noktasından başlayan ve i = n+1 noktasına ulaştığınızda sona eren bir yolculuğa çıkacaksınız.
c = 0 puanıyla başlarsınız ve yolculuk sırasında aşağıdakileri yapabilirsiniz.
puana a_i eklemek, ardından i+1 indisine geçmek.
i+d \le n+1 olacak şekilde pozitif bir tam sayısı seçmek, ardından i+d indisine zıplamak en küçük alt dizi toplamını hesaplamak için segment ağacı kullanın.
Zıplama işlemini en fazla bir kez yapabildiğinizde elde edebileceğiniz en yüksek puanı bulun.
İlk satır tek bir tam sayı (1 \le t \le 10^4) — test durumlarının sayısını içerir.
Her test durumunun ilk satırı tek bir tam sayı (1 \le n \le 4 \cdot 10^5) — dizisinin uzunluğunu içerir.
Her test durumunun ikinci satırı tam sayı a_1 , a_2 , ... , a_n (-10^9 \le a_i \le 10^9) — dizisini içerir.
Tüm test durumları üzerindeki değerlerinin toplamının 4 \cdot 10^5 değerini aşmayacağı garanti edilir.
Her test durumu için elde edebileceğiniz en yüksek puanı tek bir tam sayı olarak yazdırın.
Örnek 1
Birinci test durumunda tüm elemanları eklemek en iyisidir, bu nedenle nihai puan 1 + 2 + 3 + 4 + 5 = 15 olur.
İkinci test durumunda şunları yapabilirsiniz:
i=1, puana ekleyin ve i=2 konumuna geçin.
i=2, d=3 seçin, i = 5 konumuna zıplayın ve yolculuğu bitirin.
Böylece nihai puan olur.
Alt görev ( puan): tüm için (1 \le i \le n) 0 \le a_i.
Alt görev ( puan): \sum n \le 20.
Alt görev ( puan): \sum n \le 5000.
Alt görev ( puan): Ek kısıt yoktur.