Hành Trình Chọn Trạm

Trên một tuyến đường có $n$ trạm năng lượng được đánh số từ $1$ đến $n$. Trạm thứ $i$ có điểm năng lượng là $a_i$.

Bạn cần chọn một đoạn trạm liên tiếp từ chỉ số $l$ đến chỉ số $r$ ($1 ≤ l ≤ r ≤ n$) sao cho đoạn này chứa ít nhất 3 trạm (tức là $r - l ≥ 2$). Bạn quan tâm đến 3 trạm có điểm năng lượng lớn nhất trong đoạn $[l, r]$. Tuy nhiên, khoảng cách $r - l$ giữa hai đầu đoạn càng lớn thì chi phí di chuyển càng tăng.

Hãy tìm cách chọn $l$ và $r$ sao cho tổng điểm năng lượng của 3 trạm có điểm lớn nhất trong đoạn $[l, r]$ trừ đi khoảng cách $r - l$ đạt giá trị lớn nhất.

Nói cách khác, chọn $l$ và $r$ ($1 ≤ l ≤ r ≤ n$, $r - l ≥ 2$) để giá trị $a_{i_1} + a_{i_2} + a_{i_3} - (r - l)$ đạt cực đại, trong đó $i_1, i_2, i_3$ ($l ≤ i_1 < i_2 < i_3 ≤ r$) là chỉ số của 3 trạm có điểm năng lượng lớn nhất trong đoạn $[l, r]$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $t$ ($1 ≤ t ≤ 10^5$) biểu thị số lượng bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa số nguyên $n$ ($3 ≤ n ≤ 10^5$, tổng $n$ qua tất cả các bộ dữ liệu $\sum n ≤ 10^5$) biểu thị số lượng trạm năng lượng.

Dòng thứ hai của mỗi bộ dữ liệu chứa $n$ số nguyên $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^8$) biểu thị điểm năng lượng của các trạm.

Kết quả

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất là giá trị lớn nhất của $a_{i_1} + a_{i_2} + a_{i_3} - (r - l)$ thu được từ việc chọn đoạn $[l, r]$ hợp lệ.

Chấm điểm

Subtask 1 (30 points). $\sum n ≤ 300$

Subtask 2 (70 points). $1 ≤ t ≤ 10^5$; $3 ≤ n ≤ 10^5$; $\sum n ≤ 10^5$

Ví dụ

Input

1
5
3 8 2 7 4

Output

16

Ghi chú

Trong ví dụ trên, ta chọn ba trạm tại các vị trí $i_1 = 2$, $i_2 = 4$, $i_3 = 5$ với điểm năng lượng lần lượt là $a_2 = 8$, $a_4 = 7$, $a_5 = 4$. Đoạn được chọn là $[l, r] = [2, 5]$. Giá trị thu được là $8 + 7 + 4 - (5 - 2) = 16$.