Bessie đang thử nghiệm một thiết bị cấy ghép móng mạnh mẽ có khả năng tạo ra những sóng xung kích khổng lồ. Trước mặt cô có \(N\) (\(2 \leq N \leq 10^5\)) viên gạch xếp thành một hàng, lần lượt cần công suất ít nhất \(p_0,p_1,\dots,p_{N-1}\) để phá vỡ (\(0 \leq p_i \leq 10^{18}\)).

Bessie có thể tạo công suất bằng cách đấm vào một viên gạch cụ thể, nhưng do tính chất kỳ lạ của thiết bị cấy ghép, cú đấm sẽ không tạo ra công suất nào lên chính viên gạch cô đấm. Thay vào đó, nếu cô chọn đấm viên gạch \(x\) một lần, với \(x\) là số nguyên trong \([0,N-1]\), nó tạo ra công suất \(|i-x|\) lên viên gạch \(i\) với mọi số nguyên \(i\) trong đoạn \([0,N-1]\). Công suất này cũng được cộng dồn, nên tác dụng công suất \(2\) hai lần lên một viên gạch sẽ tạo tổng công suất \(4\) lên viên gạch đó.

Hãy xác định số cú đấm ít nhất cần thiết để phá vỡ tất cả các viên gạch.

Dữ liệu vào

Dòng đầu tiên chứa \(T\) (\(1 \leq T \leq 100\)), biểu diễn số bộ test.

Dòng \(2t\) chứa một số nguyên \(N\), là số viên gạch trong bộ test \(t\).

Dòng \(2t+1\) chứa \(N\) số \(p_0,p_1, \ldots, p_{N-1}\) cách nhau bởi dấu cách, biểu diễn viên gạch \(i\) cần công suất \(p_i\) để bị phá vỡ.

Đảm bảo tổng tất cả các giá trị \(N\) trong một input không vượt quá \(5\cdot 10^5\).

Dữ liệu ra

In \(T\) dòng, dòng thứ \(i\) là đáp án của bộ test thứ \(i\).

Ví dụ

6
5
0 2 4 5 8
5
6 5 4 5 6
5
1 1 1 1 1
5
12 10 8 6 4
7
6 1 2 3 5 8 13
2
1000000000000000000 1000000000000000000

2
3
2
4
4
2000000000000000000

Phân nhóm

• Input 2: Mọi \(p_i\) đều bằng nhau.
• Inputs 3-6: \(N\le 100\).
• Inputs 7-14: Không có ràng buộc bổ sung.

Nguồn

USACO 2025 January Contest, Platinum — Shock Wave

Đề bài: https://usaco.org/index.php?page=viewproblem2&cpid=1477

Tác giả đề: Suhas Nagar