You are given an array x[1 . . . n] and a number m. For all i from 1 to n−m+ 1 find the minimum among x[i], x[i + 1], . . . , x[i + m − 1] and return the sum of those minima.

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <vector>

#include <stack>

#include <map>

#include <set>

#include <queue>

#include <iomanip>

#include <string>

#include <ctime>

#include <list>

typedef unsigned char byte;

#define pb push_back

#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)

#define local freopen("in.txt","r",stdin)

#define pi acos(-1)

using namespace std;

const int maxn = 3e7 + ;

const long long MAX = (1LL<<) - ;

const long long MIN = -(1LL<<);

const long long STD = 1LL << ;

const long long TR = 1ll << ;

long long a, b , c , ans =   ,front =  , rear = ;

int p[maxn] , q[maxn];

int n , m , k;

inline int read()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int main(int argc,char *argv[])

{

    freopen("minima.in","r",stdin);

    freopen("minima.out","w",stdout);

  //local;

  //cout <<( (-7)%5) << endl;

  //return 0;

  scanf("%d%d%d%I64d%I64d%I64d",&n,&m,&k,&a,&b,&c);

  for(int i =  ; i <= k ; ++ i) p[i]=read();

  for(int i = k +  ; i <= n ; ++ i)

  {

       long long newval = 1LL * p[i-] * a + p[i - ] * b + c;

       if (newval < )

       {

           if(-newval>=STD) newval = newval % STD ;

           if(newval<-TR) newval+=STD;

       }

       else

       {

           if(newval>=STD) newval = newval % STD ;

           if(newval>=TR) newval-=STD;

       }

       p[i] = newval;

  }

  if (m > n) m = n;

  q[rear++] = ;

  for(int i =  ; i <= m ; ++ i)

   {

          while(front < rear && p[i] < p[q[rear-]])

         rear--;

       q[rear++] = i;

   }

  ans += p[q[front]];

  for(int i = m+ ; i <= n ; ++ i)

   {

          while(front < rear && i - q[front] >= m)

           front++;

          while(front < rear && p[i] < p[q[rear-]])

         rear--;

       q[rear++] = i;

       ans += p[q[front]];

   }

  printf("%I64d\n",ans);

  return ;

}