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

-----Examples-----
Sample Input:
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
Sample Output:
7
2
2
0
4

Source: kattis | Difficulty: HARD


Solutions: