Two arrays of integers a and b are given, both sorted in
non-decreasing order. Print the distinct values of a that do not appear
in b, in non-decreasing order. In other words, compute A \ B, where
A and B are the sets of values from the two arrays.
The required algorithm is a two-pointer merge variant that
traverses both arrays exactly once (O(n + m)).
Input:
The program reads from standard input:
- a natural number n, followed by n integers (array a);
- a natural number m, followed by m integers (array b).
- 1 <= n, m <= 1000
- -1000000 <= values <= 1000000
- the arrays are sorted in non-decreasing order and may contain duplicates
Output:
The program prints on the first line the number k of distinct values from
a that do not appear in b. If k > 0, the second line contains the
k values in non-decreasing order, separated by a single space. If
k = 0, no further line is printed.
Example:
Input:
6
1 2 3 4 5 6
3
2 4 6
Output:
3
1 3 5