Problem G
Maximal Sequences

The problem is simple. You are given a long sequence of integers $a_1,a_2,\dots ,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\le n\le {10}^5$. The second line contains $n$ integers $a_1,\dots ,a_n$. Each integer $a_j$ lies between 0 and $2^{31}-1$.

The third line contains a single integer $q\ge 1$ indicating the number of queries to process. Then $q$ lines follow, each starting with two integers $1\le i\le n$ and $1\le m\le {10}^5$, followed by $m$ distinct integers $b_1,\dots ,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},\dots ,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