×

计蒜客

  1. 题库
  2. Hello 2019
  3. 问答
  • 10.91%
  • 524288K

A digital string is "good": when it contains a subsequence $9102$ and does not contain a subsequence $8102$.

The bad value of a string is defined as how many characters are to remove at least, so that the string satisfies the "good" property. Output -1 if the string cannot satisfy the "good" property by removing some characters (0 or maybe more).

Input

The first line contains two integers $n, Q$$(1\leq n,Q\leq2*10^5)$. Where $n$ is the length of the string and $Q$ is the number of queries.

The second line contains a string $s$ that consists entirely of decimal numbers.

The next $Q$ line, each line contains two integers $l, r$$(1\leq l\leq r\leq n)$, denoting a query.

Output

For each query, output an answer which is the bad value of the substring $s_ls_{l+1} \cdots s_r$ from $s$.

样例输入

8 3
88988102
1 8
2 8
1 7

样例输出

4
3
-1

想挑战这道题吗

  • main.c