对 \((i, a_i)\) 求出下凸包，那么一条凸包的斜率非正的切线是候选答案。
只考虑切凸包上第 \(i\) 个点的切线，那么斜率的左边界是过凸包第 \(i\) 和第 \(i + 1\) 个点的直线斜率，右边界是过凸包第 \(i - 1\) 和第 \(i\) 个点的直线斜率。最优方案的切线斜率一定要么贴着左边界，要么贴着右边界，分类取个 \(\max\) 即可。
注意斜率要是整数，上/下取整处理一下即可。
时间复杂度 \(O(n)\)。
code
// Problem: P9936 [NFLSPC #6] 等差数列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9936
// Memory Limit: 1 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 100100;
ll n, a[maxn], stk[maxn], top;
struct node {
ll x, y;
node(ll a = 0, ll b = 0) : x(a), y(b) {}
} b[maxn];
inline node operator + (const node &a, const node &b) {
return node(a.x + b.x, a.y + b.y);
}
inline node operator - (const node &a, const node &b) {
return node(a.x - b.x, a.y - b.y);
}
inline ll operator * (const node &a, const node &b) {
return a.x * b.y - a.y * b.x;
}
inline ll f(ll n) {
return n * (n + 1) / 2;
}
void solve() {
scanf("%lld", &n);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
b[i] = node(i, a[i]);
}
top = 0;
for (int i = 1; i <= n; ++i) {
while (top >= 2 && (b[stk[top]] - b[stk[top - 1]]) * (b[i] - b[stk[top - 1]]) >= 0) {
--top;
}
stk[++top] = i;
}
ll ans = 1e18;
for (int i = 1; i <= top; ++i) {
ldb l = -1.1e9, r = 0;
if (i > 1) {
r = min(r, (ldb)(b[stk[i]].y - b[stk[i - 1]].y) / (b[stk[i]].x - b[stk[i - 1]].x));
}
if (i < top) {
l = max(l, (ldb)(b[stk[i]].y - b[stk[i + 1]].y) / (b[stk[i]].x - b[stk[i + 1]].x));
}
for (ll x = ceil(l); x <= r && x - l <= 2; ++x) {
ans = min(ans, a[stk[i]] * n - x * f(stk[i] - 1) + x * f(n - stk[i]));
}
for (ll x = floor(r); x >= l && r - x <= 2; --x) {
ans = min(ans, a[stk[i]] * n - x * f(stk[i] - 1) + x * f(n - stk[i]));
}
}
for (int i = 1; i <= n; ++i) {
ans -= a[i];
}
printf("%lld\n", ans);
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}