讨论一个有些难度的算法题

//不知道行不行
#include <math.h>
#include <time.h>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <fstream>
#include <algorithm>
#include <string>
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <bitset>
using namespace std;
typedef long long item;
typedef long long _ll;
#define ls s<<1
#define rs s<<1|1
#define ri register int
#define mod 1000007
inline item read()
{
item f = 1, ret = 0;
char c = getchar();
while (c < 48 || c>57){if (c == '-')f = -f;c = getchar();}
while (c >= 48 && c <= 57){ret = ret * 10 + c - 48;c = getchar();}
return f * ret;
}
int n, q[2000004], h, t, ll, rr;
_ll x, dat[2000004], sum1, sum2, ans = 0x3f3f3f3f3f3f3f3f;
void check(_ll & sum,int k) {
sum = x * k; h = t = 0;
for (ri i = n+k; i > n; --i) {
while (h != t && dat[i] <= dat[q[t-1]])
--t;
q[t++] = i;
}
for (ri i = n; i; --i) {
if (h!=t&&q[h] > i + k) {
++h;
}
while (h != t && dat[i] <= dat[q[t - 1]])
--t;
q[t++] = i;
sum += dat[q[h]];
}
}
int main()
{
//freopen("d:\\yx.txt", "r", stdin);
n = read();
for (ri i = 1; i <= n; ++i) {
dat[i + n] = dat[i] = read();
}
x = read();
ll = 0; rr = n - 1;
while (ll <= rr) {
int mid = (ll + rr) >> 1;
check(sum1, mid);
check(sum2, mid + 1);
if (sum1 <= sum2) {
rr = mid - 1;
}
else
ll = mid + 1;
sum1 = min(sum1, sum2);
if (sum1 < ans)
ans = sum1;
}
printf("%lld", ans);
return 0;
}

很可惜，这个题用二分是不行的，转动总次数和花费的多少并不存在固定的单调关系，举个例子是6 [1,1,1,5,6,7] 5
不转动的最小花费是21，
转1次的最小花费是20（价格列表变成[7,1,1,1,5,6]），按照[1,1,1,1,5,6]的价格购买这些商品
（商品0,1,2在未转动的时候买，商品3,4,5在转动1次之后买）
转2次的最小花费是20（价格列表变成[6,7,1,1,1,5]），按照[1,1,1,1,1,5]的价格购买这些商品
（商品0,1,2在未转动的时候买，商品3,4,5在转动2次之后买）
转3次的最小花费是21（价格列表变成[5,6,7,1,1,1]），按照[1,1,1,1,1,1]的价格购买这些商品
（商品0,1,2在未转动的时候买，商品3,4,5在转动3次之后买）

似乎感觉单调栈能够达到满分的时间复杂度，但是我在外面身边没有电脑，不能自己写一写看看对不对，就只说一说思路

我为什么觉得这个出题的模板看起来很眼熟？ccf？
看这个解析的描述似乎是单调栈