A row of n commemorative coins lies on a table. Coin i has a value h[i] engraved on its heads side and a value t[i] engraved on its tails side. Independently for every coin, you may choose whether it rests heads-up or tails-up; once all choices are made, each coin shows exactly one of its two engraved values face-up.
Call a positive integer v concealable if there exists some choice of orientation for every coin — made all at once, in advance — such that v does not appear face-up on any coin in the row. Note that a coin whose heads and tails values are both equal to v will always show v no matter which way it rests, so the existence of such a coin rules out concealing v.
Given the engravings on all n coins, find the smallest concealable positive integer. It is guaranteed that at least one concealable value exists.
Line 1: a single integer n. Line 2: n integers h[1..n] — the heads-side values. Line 3: n integers t[1..n] — the tails-side values.
Print a single integer: the smallest concealable positive integer.
Example 1
Input
3 1 2 4 2 4 4
Expected
1
Explanation
Coin 3 shows 4 on both faces, so 4 is permanently visible no matter its orientation, but no coin is permanently locked to 1 (coin 1 has heads 1 but a different tails value 2, so flipping it hides 1, and no other coin shows 1 at all). Since 1 is not permanently forced, it is already concealable, making the answer 1.
Example 2
Input
4 1 2 3 4 1 3 4 5
Expected
2
Explanation
Coin 1 shows 1 on both faces, so 1 is permanently visible and cannot be concealed. Coin 2 shows 2 on heads but 3 on tails (not locked), and no other coin shows 2 at all, so resting coin 2 tails-up hides 2 entirely. Since 1 fails but 2 succeeds, the smallest concealable value is 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →