F - A Set Problem Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

問題文

N 個の整数からなる整数の集合 S=\{S_1,S_2,\dots,S_N\} が与えられるので、以下の Q 個の質問に答えてください。

  • M 個の整数からなる整数の集合 T=\{T_1,T_2,\dots,T_M\} が与えられるので、 S と T の和集合には何個の整数が含まれるか答えよ。

制約

  • 入力は全て整数
  • 1 \le N \le 2 \times 10^5
  • 1 \le S_i \le 10^9
  • i \neq j ならば S_i \neq S_j
  • 全ての質問は以下の制約を満たす
    • 1 \le M
    • i \neq j ならば T_i \neq T_j
  • ひとつの入力に含まれる M の総和は 2 \times 10^5 を超えない

入力

入力は以下の形式で標準入力から与えられる。

N
S_1 S_2 \dots S_N
Q
\rm{Query}_{1}
\rm{Query}_{2}
\vdots
\rm{Query}_{Q}

但し、 \rm{Query}_{i} は i 個目の質問を表す。 各質問は以下の形式で与えられる。

M
T_1 T_2 \dots T_M

出力

Q 行にわたって出力せよ。
i 行目には i 個目の質問に対する答えを整数として出力せよ。

入力例 1

5
2 3 5 7 11
5
6
1 3 5 7 9 11
6
12 10 8 6 4 2
3
5 7 3
3
8 4 6
12
3 2 1 6 5 4 9 8 7 12 11 10

出力例 1

7
10
5
8
12

この入力では、 S=\{2,3,5,7,11\} であり、質問が 5 つ与えられます。

  • 1 つ目の質問では、 T=\{1,3,5,7,9,11\} です。 S と T の和集合は \{1,2,3,5,7,9,11\} であり、ここには 7 個の整数が含まれます。
  • 2 つ目の質問では、 T=\{12,10,8,6,4,2\} です。 S と T の和集合は \{2,3,4,5,6,7,8,10,11,12\} であり、ここには 10 個の整数が含まれます。

Problem Statement

Given a set of N integers, S=\{S_1,S_2,\dots,S_N\}, answer Q queries in the following format:

  • given a set of M integers, T=\{T_1,T_2,\dots,T_M\}, find how many integers the union of S and T contains.

Constraints

  • All values in the input are integers.
  • 1 \le N \le 2 \times 10^5
  • 1 \le S_i \le 10^9
  • If i \neq j, then S_i \neq S_j.
  • All queries satisfy the following conditions:
    • 1 \le M
    • If i \neq j, then T_i \neq T_j.
  • The sum of M in an input does not exceed 2 \times 10^5.

Input

The input is given from Standard Input in the following format:

N
S_1 S_2 \dots S_N
Q
\rm{Query}_{1}
\rm{Query}_{2}
\vdots
\rm{Query}_{Q}

Here, \rm{Query}_{i} denotes the i-th query. Each query is given in the following format:

M
T_1 T_2 \dots T_M

Output

Print Q lines.
The i-th line should contain the answer to the i-th query as an integer.

Sample Input 1

5
2 3 5 7 11
5
6
1 3 5 7 9 11
6
12 10 8 6 4 2
3
5 7 3
3
8 4 6
12
3 2 1 6 5 4 9 8 7 12 11 10

Sample Output 1

7
10
5
8
12

In this input, S=\{2,3,5,7,11\}, and five queries are given.

  • In the first query, T=\{1,3,5,7,9,11\}. The union of S and T is \{1,2,3,5,7,9,11\}, which contains seven integers.
  • In the second query, T=\{12,10,8,6,4,2\}. The union of S and T is \{2,3,4,5,6,7,8,10,11,12\}, which contains ten integers.