---

单调队列优化dp

对于不是常数转移的dp转移，我们都可以考虑单调队列转移

然而我们要把数组开大

#include
    
     #include
     
      #include
      
       using namespace std;int read(){    int s=0,f=1;    char in=getchar();    while(in<'0'||in>'9')    {        if(in=='-')            f=-1;        in=getchar();    }    while(in>='0'&&in<='9')    {        s=(s<<1)+(s<<3)+in-'0';        in=getchar();    }    return s*f;}int data[301000];int dp[301000];struct node{    int value;    int rank;};node queue[2010000];int head=1,tail;int n,l,r;void push(int x,int pos){    while(queue[tail].value
       
        =head)        tail-=1;    tail+=1;    queue[tail].value=x;    queue[tail].rank=pos;}int top(){    return queue[head].value;}void pop(int pos){    while(queue[head].rank