×

# 计蒜客

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