#include <bits/stdc++.h>

using namespace std;
#include "peru.h"

long long seg[2500000*4];
long long mod = 1000000007;
void update(int p,int l,int r,int idx,int val){
    if(l==r){
        seg[p] = val;
        return ;
    }
    int md = (l+r)/2;
    if(idx<=md)update(p*2,l,md,idx,val);
    else update(p*2+1,md+1,r,idx,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
long long query(int p,int l,int r,int lq,int rq){
    if(l>=lq&&r<=rq)return seg[p];
    if(r<lq||l>rq)return 1e18;
    int md = (l+r)/2;
    return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
int solve(int n, int k,int* ss){
    int arr[n+1];
    for(int i = 1;i<=n*4;i++)seg[i] = 1e18;
    for(int i = 1;i<=n;i++)arr[i] = ss[i-1];
    long long a3[n+1] = {0};
    for(int i = 1;i<=n;i++){
        long long mi = arr[i];a3[i] = 1e18;
        for(int j = i-1;j>=max(0,i-k);j--){
            a3[i] = min(a3[i],a3[j]+mi);
            mi = max(mi,arr[j]);
        }
    }
    long long ans2 = 0 , po2 = 1;
    for(int i = n;i>=1;i--){
        ans2+=(a3[i]*po2)%mod;
        po2*=23;po2%=mod;
    }
    long long dp[n+1] = {0};
    update(1,0,n,0,0);
    multiset<long long> s;
    deque<pair<long long,long long>> st;
    for(int i = 1;i<=n;i++){
        long long mi = dp[i-1];
        while(!st.empty()&&arr[st.back().second]<=arr[i]){
            s.erase(s.lower_bound(st.back().first+arr[st.back().second]));
            mi = min(mi,st.back().first);
            st.pop_back();
        }
        st.push_back({mi,i});
        s.insert(mi+arr[i]);
        int la = 0;
        while(!st.empty()&&st[0].second<=i-k){
            la = st[0].second;
            s.erase(s.lower_bound(arr[st[0].second]+st[0].first));
            st.pop_front();
        }
        if(la<i-k){
        int e = st[0].second;
        s.erase(s.lower_bound(arr[e]+st[0].first));
        st.pop_front();
        long long vl = query(1,0,n,i-k,e-1);
        s.insert(arr[e]+vl);
        st.push_front({vl,e});
        }
        dp[i] =(*s.begin());
        update(1,0,n,i,dp[i]);
    }
    long long ans = 0 , po = 1;
    for(int i = n;i>=1;i--){
        ans+=(dp[i]*po)%mod;ans%=mod;
        po*=23;po%=mod;
    }
    return ans2;
}

implementer.cpp: In function ‘int main()’:
implementer.cpp:34:13: error: ‘fout’ was not declared in this scope; did you mean ‘out’?
   34 |     fprintf(fout, "%d\n", sol);
      |             ^~~~
      |             out
implementer.cpp: In function ‘char nextch()’:
implementer.cpp:15:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |     if (pos == BUF_SIZE) fread(buf, BUF_SIZE, 1, fin), pos = 0;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
answer.code: In function ‘int solve(int, int, int*)’:
answer.code:33:21: error: no matching function for call to ‘max(long long int&, int&)’
   33 |             mi = max(mi,arr[j]);
      |                  ~~~^~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:33:21: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   33 |             mi = max(mi,arr[j]);
      |                  ~~~^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:33:21: note:   deduced conflicting types for parameter ‘const _Tp’ (‘long long int’ and ‘int’)
   33 |             mi = max(mi,arr[j]);
      |                  ~~~^~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:33:21: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   33 |             mi = max(mi,arr[j]);
      |                  ~~~^~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:33:21: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘long long int’
   33 |             mi = max(mi,arr[j]);
      |                  ~~~^~~~~~~~~~~