×

- 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).

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.

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