You are given a sequence of n integers S and a sequence of different q integers T. Write…
- User
You are given a sequence of n integers S and a sequence of different q integers T. Write a program which outputs C, the number of integers in T which are also in the set S.
Notes
Constraints
- Elements in S is sorted in ascending order
- n ≤ 100000
- q ≤ 50000
- 0 ≤ an element in S ≤ 109
- 0 ≤ an element in T ≤ 109 Input
In the first line n is given. In the second line, n integers are given. In the third line q is given. Then, in the fourth line, q integers are given.
Output
Print C in a line.
Examples
Input
5 1 2 3 4 5 3 3 4 1
Output
3
Input
3 1 2 3 1 5
Output
0
Input
5 1 1 2 2 3 2 1 2
Output
2
Assistant
We need to output the number of integers from T that are present in S. S is sorted. n up to 100k, q up to 50k. Could use binary search for each query. Complexity O((n+q) log n) or O(q log n). That's fine.
Alternatively, could use set or hash set. But given S sorted, binary search is straightforward.
We'll implement solve() that reads input, stores S list, then for each t in T, binary search (using bisect) to check if t in S. Count.
But careful: constraints: S can have duplicate values? Input example 3 shows S: 1 1 2 2 3, which has duplicates. So we need to count whether each T element is present at least once. Using binary search to find if element exists. Since S sorted, we can use bisect_left and compare with S[bisect_left] equals t.
We'll read input via sys.stdin.read().split() for speed.
We'll output count.
Implementation:
def solve(): import sys, bisect data = sys.stdin.read().split() if not data: return it = iter(data) n = int(next(it)) S = [int(next(it)) for _ in range(n)] q = int(next(it)) T = [int(next(it)) for _ in range(q)] # optional: if we want to sort T? not needed. cnt = 0 for t in T: idx = bisect.bisect_left(S, t) if idx < n and S[idx] == t: cnt += 1 sys.stdout.write(str(cnt))
That's it.
But be careful: the input format says "Elements in S is sorted in ascending order". So we can rely on that.
We'll produce final answer.
Note: The user message is a problem statement. We just need to output code? The user asks "You are given ... Write a program ...". Usually in these chat prompts, we need to provide a solution code. So I'll respond with the Python code.
Thus final. ```python
import sys import bisect
def solve() -> None: data = sys.stdin.read().split() if not data: return
it = iter(data) n = int(next(it)) S = [int(next(it)) for _ in range(n)] q = int(next(it)) T = [int(next(it)) for _ in range(q)] cnt = 0 for t in T: # S is sorted → use binary search idx = bisect.bisect_left(S, t) if idx < n and S[idx] == t: cnt += 1 sys.stdout.write(str(cnt))if name == "main": solve()