{"problem":{"name":"E. New Year and Old Subsequence","description":{"content":"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_","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF750E"},"statements":[{"statement_type":"Markdown","content":"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.\n\nThe _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.\n\nLimak 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).\n\n## Input\n\nThe first line of the input contains two integers _n_ and _q_ (4 ≤ _n_ ≤ 200 000, 1 ≤ _q_ ≤ 200 000) — the length of the string _s_ and the number of queries respectively.\n\nThe second line contains a string _s_ of length _n_. Every character is one of digits '_0_'–'_9_'.\n\nThe _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.\n\n## Output\n\nFor each query print the ugliness of the given substring.\n\n[samples]\n\n## Note\n\nIn the first sample:\n\n*   In the first query, _ugliness_(\"_20166766_\") = 4 because all four sixes must be removed.\n*   In the second query, _ugliness_(\"_2016676_\") = 3 because all three sixes must be removed.\n*   In the third query, _ugliness_(\"_0166766_\") =  - 1 because it's impossible to remove some digits to get a nice string.\n\nIn the second sample:\n\n*   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.\n*   In the third query, _ugliness_(\"_016662091670_\") = 1. It's optimal to remove the last digit '_6_', what gives a nice string \"_01666209170_\".","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"一个字符串 #cf_span[t] 被称为 _nice_，当且仅当字符串 \"_2017_\" 作为 *子序列* 出现在 #cf_span[t] 中，但字符串 \"_2016_\" 不作为 *子序列* 出现在 #cf_span[t] 中。例如，字符串 \"_203434107_\" 和 \"_9220617_\" 是 nice 的，而字符串 \"_20016_\"、\"_1234_\" 和 \"_20167_\" 不是 nice 的。\n\n一个字符串的 _ugliness_ 是为了获得一个 nice 字符串所需移除的最少字符数。如果无法通过移除字符使字符串变成 nice，则其 ugliness 为 #cf_span[ - 1]。\n\nLimak 有一个长度为 #cf_span[n] 的字符串 #cf_span[s]，字符索引从 #cf_span[1] 到 #cf_span[n]。他向你提出 #cf_span[q] 个查询。在第 #cf_span[i] 个查询中，你需要计算并输出字符串 #cf_span[s] 中从索引 #cf_span[ai] 开始、到索引 #cf_span[bi] 结束（包含两端）的 *子串* 的 ugliness。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[4 ≤ n ≤ 200 000], #cf_span[1 ≤ q ≤ 200 000]) —— 分别表示字符串 #cf_span[s] 的长度和查询次数。\n\n第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]。每个字符都是数字 '_0_' 到 '_9_' 之一。\n\n接下来的 #cf_span[q] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai ≤ bi ≤ n])，描述第 #cf_span[i] 个查询中的子串。\n\n对于每个查询，请输出对应子串的 ugliness。\n\n在第一个样例中：\n\n在第二个样例中：\n\n## Input\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[q] (#cf_span[4 ≤ n ≤ 200 000], #cf_span[1 ≤ q ≤ 200 000]) —— 分别表示字符串 #cf_span[s] 的长度和查询次数。第二行包含一个长度为 #cf_span[n] 的字符串 #cf_span[s]。每个字符都是数字 '_0_' 到 '_9_' 之一。第 #cf_span[i] 行是接下来的 #cf_span[q] 行之一，包含两个整数 #cf_span[ai] 和 #cf_span[bi] (#cf_span[1 ≤ ai ≤ bi ≤ n])，描述第 #cf_span[i] 个查询中的子串。\n\n## Output\n\n对于每个查询，请输出对应子串的 ugliness。\n\n[samples]\n\n## Note\n\n在第一个样例中：\n\n在第一个查询中，#cf_span[ugliness(]\"_20166766_\"#cf_span[) = 4]，因为必须移除全部四个 '6'。\n\n在第二个查询中，#cf_span[ugliness(]\"_2016676_\"#cf_span[) = 3]，因为必须移除全部三个 '6'。\n\n在第三个查询中，#cf_span[ugliness(]\"_0166766_\"#cf_span[) =  - 1]，因为无法通过移除某些数字得到一个 nice 字符串。\n\n在第二个样例中：\n\n在第二个查询中，#cf_span[ugliness(]\"_01201666209167_\"#cf_span[) = 2]。最优策略是移除第一个 '2' 和最后一个 '6'，得到字符串 \"_010166620917_\"，这是一个 nice 字符串。\n\n在第三个查询中，#cf_span[ugliness(]\"_016662091670_\"#cf_span[) = 1]。最优策略是移除最后一个 '6'，得到 nice 字符串 \"_01666209170_\"。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ s \\in \\{0,1,\\dots,9\\}^n $ be a string of length $ n $.  \nLet $ T = \\text{\"2017\"} $, $ F = \\text{\"2016\"} $.  \nA substring $ s[a:b] $ is *nice* if $ T $ is a subsequence of $ s[a:b] $ and $ F $ is **not** a subsequence of $ s[a:b] $.  \n\nThe *ugliness* of a substring $ s[a:b] $ is the minimum number of characters to remove so that the result is nice. If no such removal exists, ugliness is $ -1 $.  \n\n**Constraints**  \n1. $ 4 \\le n \\le 200{,}000 $  \n2. $ 1 \\le q \\le 200{,}000 $  \n3. For each query $ i $, $ 1 \\le a_i \\le b_i \\le n $  \n\n**Objective**  \nFor each query $ i $, compute:  \n$$\nu_i = \\min \\left\\{ k \\in \\mathbb{N}_0 \\,\\middle|\\, \\exists S \\subseteq s[a_i:b_i],\\, |S| = b_i - a_i + 1 - k,\\, T \\sqsubseteq S,\\, F \\not\\sqsubseteq S \\right\\}\n$$  \nIf no such $ S $ exists, then $ u_i = -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF750E","tags":["data structures","divide and conquer","dp","matrices"],"sample_group":[["8 3\n20166766\n1 8\n1 7\n2 8","4\n3\n-1"],["15 5\n012016662091670\n3 4\n1 14\n4 15\n1 13\n10 15","\\-1\n2\n1\n-1\n-1"],["4 2\n1234\n2 4\n1 2","\\-1\n-1"]],"created_at":"2026-03-03 11:00:39"}}