Problem D
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?

Input

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

Output

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

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

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