u1s1 我做这道 *2600 的动力是 wjz 出了道这个套路的题，而我连起码的思路都没有，wtcl/kk
首先考虑怎样对某个固定的串计算答案，这显然可以 \(dp\) 解决，设 \(dp_{i,j}\) 表示考虑前 \(i\) 个字符，删去之后与 \(2017\) 的 LCS 为 \(j\)，最少需删除多少个字符，那么显然有转移方程：
- \(dp_{i,0}=\begin{cases}dp_{i-1,0}&(s[i]\neq'2')\\dp_{i-1,0}+1&(s[i]='2')\end{cases}\)
- \(dp_{i,1}=\begin{cases}dp_{i-1,0}&(s[i]\neq'0')\\\min(dp_{i-1,1}+1,dp_{i-1,0})&(s[i]='0')\end{cases}\)
- \(dp_{i,2}=\begin{cases}dp_{i-1,2}&(s[i]\neq'1'\land s[i]\neq'6')\\\min(dp_{i-1,2}+1,dp_{i-1,1})&(s[i]='1')\\dp_{i-1,2}+1&(s[i]='6')\end{cases}\)
- \(dp_{i,3}=\begin{cases}dp_{i-1,3}&(s[i]\neq'6'\land s[i]\neq'7')\\\min(dp_{i-1,3},dp_{i-1,2})&(s[i]='7')\\dp_{i-1,3}+1&(s[i]='6')\end{cases}\)
初始值为 \(dp_{0,0}=0,dp_{0,i}=-\infty(i>0)\)。
注意到像这样的常系数其次线性递推式可以写成矩阵的形式，也就是说对于每个字符 \(s_i\) 都可以找到一个 \(4\times 4\) 矩阵 \(A_i\) 使得 \(\begin{bmatrix}dp_{i,0}\\dp_{i,1}\\dp_{i,2}\\dp_{i,3}\end{bmatrix}=A_i\times\begin{bmatrix}dp_{i-1,0}\\dp_{i-1,1}\\dp_{i-1,2}\\dp_{i-1,3}\end{bmatrix}\)，也就是说对于一组询问 \([l,r]\)，如果我们记 \(B_i=\begin{bmatrix}dp_{i,0}\\dp_{i,1}\\dp_{i,2}\\dp_{i,3}\end{bmatrix}\)，那么有 \(B_r=A_r\times B_{r-1}=A_r\times A_{r-1}\times B_{r-2}=A_r\times A_{r-1}\times\dots A_l\times B_{l-1}\)，而显然有 \(B_{l-1}=\begin{bmatrix}0\\-\infty\\-\infty\\-\infty\end{bmatrix}\)，故最终的答案为 \((\prod\limits_{i=l}^rA_i)\times \begin{bmatrix}0\\-\infty\\-\infty\\-\infty\end{bmatrix}\)。不难发现这个东西是以区间乘法的形式出现的，而矩阵又不支持除法，故可以想到我们喜闻乐见的线段树。简单维护一下即可。
时间复杂度 \(q\omega^3\log n\)，其中 \(\omega\) 为矩阵大小，在此题中为 \(2\)。
这个套路（线段树维护矩阵乘法）就是动态 dp（ddp） 的大致思想，比较毒瘤的动态 dp 一般还需套个树剖什么的。不过由于我太懒了就暂且不继续学 ddp 了（
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
#define FILE_SIZE 1<<23
char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
inline void putc(char x){(*p3++=x);}
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=0;
while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(neg) x=(~x)+1;
}
template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=2e5;
const int INF=0x3f3f3f3f;
int n,qu;char str[MAXN+5];
struct matrix{
int a[5][5];
matrix(){memset(a,63,sizeof(a));}
matrix operator *(const matrix &rhs){
matrix ret;
for(int i=0;i<5;i++) for(int j=0;j<5;j++) for(int k=0;k<5;k++)
chkmin(ret.a[i][j],a[i][k]+rhs.a[k][j]);
return ret;
}
};
struct node{int l,r;matrix v;} s[MAXN*4+5];
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;if(l==r){
for(int i=0;i<5;i++) s[k].v.a[i][i]=0;
if(str[l]=='2') s[k].v.a[0][0]=1,s[k].v.a[0][1]=0;
if(str[l]=='0') s[k].v.a[1][1]=1,s[k].v.a[1][2]=0;
if(str[l]=='1') s[k].v.a[2][2]=1,s[k].v.a[2][3]=0;
if(str[l]=='7') s[k].v.a[3][3]=1,s[k].v.a[3][4]=0;
if(str[l]=='6') s[k].v.a[3][3]=1,s[k].v.a[4][4]=1;
return;
} int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);
s[k].v=s[k<<1].v*s[k<<1|1].v;
}
matrix query(int k,int l,int r){
if(l<=s[k].l&&s[k].r<=r) return s[k].v;
int mid=s[k].l+s[k].r>>1;
if(r<=mid) return query(k<<1,l,r);
else if(l>mid) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)*query(k<<1|1,mid+1,r);
}
int main(){
scanf("%d%d%s",&n,&qu,str+1);build(1,1,n);
while(qu--){
int l,r;scanf("%d%d",&l,&r);int ret=query(1,l,r).a[0][4];
if(ret>=INF) puts("-1");else printf("%d\n",ret);
}
return 0;
}