#pragma once
// return dat | dat[i] := ( answer of range [i - K, i) )// T : data type// f : compare function// K : width of windowtemplate<typenameT,typenameF>vector<T>SlideWindowMinimum(vector<T>&v,Ff,intK){vector<T>dat;intN=v.size();dat.resize(N+1);dat[0]=0;deque<int>q;for(inti=0;i<K-1;i++){while(!q.empty()&&(f(v[i],v[q.back()])==v[i]))q.pop_back();q.push_back(i);dat[i+1]=v[q.front()];}for(inti=K;i<N+1;i++){Tcur=v[i-1];while(!q.empty()&&(f(cur,v[q.back()])==cur))q.pop_back();q.push_back(i-1);dat[i]=v[q.front()];if(q.front()==i-K)q.pop_front();}returndat;}
#line 2 "data-structure/sliding-window-minimum.hpp"
// return dat | dat[i] := ( answer of range [i - K, i) )// T : data type// f : compare function// K : width of windowtemplate<typenameT,typenameF>vector<T>SlideWindowMinimum(vector<T>&v,Ff,intK){vector<T>dat;intN=v.size();dat.resize(N+1);dat[0]=0;deque<int>q;for(inti=0;i<K-1;i++){while(!q.empty()&&(f(v[i],v[q.back()])==v[i]))q.pop_back();q.push_back(i);dat[i+1]=v[q.front()];}for(inti=K;i<N+1;i++){Tcur=v[i-1];while(!q.empty()&&(f(cur,v[q.back()])==cur))q.pop_back();q.push_back(i-1);dat[i]=v[q.front()];if(q.front()==i-K)q.pop_front();}returndat;}