作为一道单调队列优化 DP 的几乎板子题，这题把我一个朴素 DP 放过去太合适吧。

建议加强数据，只需要制造 $N=2\times10^5,L=1,R=N$ 的数据即可卡死朴素 DP 到 $O(n^2)$。附上数据生成器源码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5, L = 1, R = N;
const int Aupper = 1000, Alower = -1000;
const char *fileName = "file.in";

int main() {
	srand(time(NULL));
	FILE *file = fopen(fileName, "w");
	fprintf(file, "%d %d %d\n", N, L, R);
	for (int i = N; i--; fprintf(file, "%d%c", rand() % (Aupper - Alower + 1) + Alower, " \n"[i == 0]));
	return 0;
}