Maximal Sequences

The problem is simple. You are given a long sequence of
integers $a_1, a_2, \ldots , a_
n$. Then you are given a query consisting of a *start
index* $i$ and a
subset of integers $B$.
What is the longest consecutive subsequence of the given
sequence that starts at position $i$ and contains only integers in
$B$?

Simple, right?

The first line of input contains a single integer $1 \leq n \leq 10^5$. The second line contains $n$ integers $a_1, \ldots , a_ n$. Each integer $a_ j$ lies between 0 and $2^{31}-1$.

The third line contains a single integer $q \geq 1$ indicating the number of queries to process. Then $q$ lines follow, each starting with two integers $1 \leq i \leq n$ and $1 \leq m \leq 10^5$, followed by $m$ distinct integers $b_1, \ldots , b_ m$. Each integer $b_ j$ lies between 0 and $2^{31}-1$.

Finally, you are guaranteed the sum of all values $m$ over all queries is at most $10^5$.

For each query, output a single line with the length of the longest prefix of $a_ i, a_{i+1}, \ldots , a_ n$ that only contains integers from $B$.

Sample Input 1 | Sample Output 1 |
---|---|

7 1 2 3 1 2 1 1 5 1 3 1 2 3 1 2 1 2 2 2 2 3 3 2 1 2 4 2 1 2 |
7 2 2 0 4 |

Sample Input 2 | Sample Output 2 |
---|---|

10 1 2 3 4 5 6 7 8 9 10 5 1 10 1 2 3 4 5 6 7 8 9 10 7 10 1 2 3 4 5 6 7 8 9 10 5 5 1 14 7 6 5 2 6 6 3 4 2 7 5 1 1 1 |
10 4 3 6 1 |