New Year and Old Subsequence

题意翻译

## 题目描述 定义一个数字串满足性质$nice$当且仅当：该串包含子序列$2017$，且不包含子序列$2016$。 定义一个数字串的函数$ugliness$为：该串至少删去几个字符，可以使得剩余串满足性质$nice$；如果该串没有满足性质$nice$的子序列，则该串的$ugliness$是$-1$。 给定一个长度为$n$的字符串$t$，和$q$次询问，每次询问用$(l,r)$表示。对于每次询问，回答$ugliness(t[l,r])$。 ## 输入输出格式 ### 输入格式： 第一行输入两个整数$n,q$ ，其中$n$是字符串$s$的长度，$q$是询问的个数。 第二行输入完全由十进制数字组成的字符串$s$。 接下来的$n$行，每行输入两个整数$l,r$，描述一个询问。 ### 输出格式： 对于每个询问，输出一行答案。 ### 数据范围： $$ 4 \leq n \leq 200000,1 \leq q \leq 200000,1 \leq l \leq r \leq n $$

题目描述

A string $ t $ is called nice if a string "2017" occurs in $ t $ as a subsequence but a string "2016" doesn't occur in $ t $ as a subsequence. For example, strings "203434107" and "9220617" are nice, while strings "20016", "1234" and "20167" aren't nice. The ugliness of a string is the minimum possible number of characters to remove, in order to obtain a nice string. If it's impossible to make a string nice by removing characters, its ugliness is $ -1 $ . Limak has a string $ s $ of length $ n $ , with characters indexed $ 1 $ through $ n $ . He asks you $ q $ queries. In the $ i $ -th query you should compute and print the ugliness of a substring (continuous subsequence) of $ s $ starting at the index $ a_{i} $ and ending at the index $ b_{i} $ (inclusive).

输入输出格式

输入格式

The first line of the input contains two integers $ n $ and $ q $ ( $ 4<=n<=200000 $ , $ 1<=q<=200000 $ ) — the length of the string $ s $ and the number of queries respectively. The second line contains a string $ s $ of length $ n $ . Every character is one of digits '0'–'9'. The $ i $ -th of next $ q $ lines contains two integers $ a_{i} $ and $ b_{i} $ ( $ 1<=a_{i}<=b_{i}<=n $ ), describing a substring in the $ i $ -th query.

输出格式

For each query print the ugliness of the given substring.

输入输出样例

输入样例 #1

8 3
20166766
1 8
1 7
2 8

输出样例 #1

4
3
-1

输入样例 #2

15 5
012016662091670
3 4
1 14
4 15
1 13
10 15

输出样例 #2

-1
2
1
-1
-1

输入样例 #3

4 2
1234
2 4
1 2

输出样例 #3

-1
-1

说明

In the first sample: - In the first query, $ ugliness( $ "20166766" $ )=4 $ because all four sixes must be removed. - In the second query, $ ugliness( $ "2016676" $ )=3 $ because all three sixes must be removed. - In the third query, $ ugliness( $ "0166766" $ )=-1 $ because it's impossible to remove some digits to get a nice string. In the second sample: - In the second query, $ ugliness( $ "01201666209167" $ )=2 $ . It's optimal to remove the first digit '2' and the last digit '6', what gives a string "010166620917", which is nice. - In the third query, $ ugliness( $ "016662091670" $ )=1 $ . It's optimal to remove the last digit '6', what gives a nice string "01666209170".

题意翻译

## 题目描述 定义一个数字串满足性质$nice$当且仅当：该串包含子序列$2017$，且不包含子序列$2016$。 定义一个数字串的函数$ugliness$为：该串至少删去几个字符，可以使得剩余串满足性质$nice$；如果该串没有满足性质$nice$的子序列，则该串的$ugliness$是$-1$。 给定一个长度为$n$的字符串$t$，和$q$次询问，每次询问用$(l,r)$表示。对于每次询问，回答$ugliness(t[l,r])$。 ## 输入输出格式 ### 输入格式： 第一行输入两个整数$n,q$ ，其中$n$是字符串$s$的长度，$q$是询问的个数。 第二行输入完全由十进制数字组成的字符串$s$。 接下来的$n$行，每行输入两个整数$l,r$，描述一个询问。 ### 输出格式： 对于每个询问，输出一行答案。 ### 数据范围： $$ 4 \leq n \leq 200000,1 \leq q \leq 200000,1 \leq l \leq r \leq n $$