Skip to content
TheChatArchiveThe Chat Archive
DeepSeekDeepseek v3.2· deepseekHugging Face Frontier Reasoning Traces

You are given a sequence of n integers S and a sequence of different q integers T. Write…

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

  2. DeepSeek 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()