Anya wants to celebrate New Year's, however, Loid is only willing to do so if she studies hard for her exams. Initially, Anya is playing with a permutation
of
integers from
to
. In order to test her abilities, Loid gives her
independent queries to answer. Each query is a set
of distinct indices in the permutation. For each index
in
, Anya must set the value of
to any integer
such that
is not in
, and
. Then, Anya creates a graph by drawing an undirected edge from
to
, for all
. The answer to the query is the maximum number of connected components she can obtain. Queries are independent, so the permutation is restored after every query. Unfortunately, Anya is not smart enough to solve this problem. Please help Anya cheat and pass the test!
Constraints




is a permutation of the integers
.
The elements of
are distinct.
The sum of
across all queries does not exceed
.
Subtask 1 [30%]
For
,
, and
.
Subtask 2 [70%]
No additional constraints.
Input Specification
The first line contains
space-separated integers
and
.
The next line contains
space-separated integers, representing the permutation
.
The next
lines contain the
queries. The first line of each query is an integer
, the size of the set. The second line of each query contains
integers, representing the set
.
Output Specification
Output
lines, where the
th line contains the maximum number of connected components obtainable for each query.
Sample Input
Copy
6 2
3 6 5 1 4 2
2
2 6
3
3 4 2
Sample Output
Copy
1
3
Explanation for Sample
In the first query, it can be shown that the only possible number of connected components obtainable is
, for example by turning
into
.
In the second query, turning
into
is optimal.
Comments