Minimum Modifications for Non‐crossing Color Connections

You are given two sequences: \(a = \{a_1,a_2,\dots,a_n\}\) and \(b = \{b_1,b_2,\dots,b_m\}\). The sequence \(a\) has length \(n\) and contains exactly \(k\) different colors (with colors numbered from \(1\) to \(k\)); it is guaranteed that every color from \(1\) to \(k\) appears at least once in \(a\). The sequence \(b\) has length \(m\) and each \(b_i\) is one of the colors \(1,2,\dots,k\) (note that \(b\) might not contain all \(k\) colors).

You are allowed to change some positions in \(b\) to obtain a new sequence \(b'\) (of the same length \(m\)), with the restriction that each \(b'_i\) must be one of \(1,2,\dots,k\), and importantly, \(b'\) must contain every color from \(1\) to \(k\) at least once.

Now, we draw a colored line segment for each color between the two sequences. In particular, for each color \(c\), let \(i_c\) be the position of the first occurrence of \(c\) in \(a\) and \(j_c\) be the position of the first occurrence of \(c\) in \(b'\). Then we draw a line segment connecting the point at position \(i_c\) (in \(a\)) and the point at position \(j_c\) (in \(b'\)). The resulting drawing must satisfy the property that the line segments for any two different colors do not cross. Formally, if \(c_1\) and \(c_2\) are two distinct colors and if \(i_{c_1} < i_{c_2}\) then we must have \(j_{c_1} < j_{c_2}\).

You are to compute the minimum number of modifications (i.e. the number of positions where \(b_i \neq b'_i\)) needed so that there exists a sequence \(b'\) satisfying:

• Each \(b'_i \in \{1,2,\dots,k\}\).
• All colors \(1,2,\dots,k\) appear in \(b'\).
• If we denote by \(q_1,q_2,\dots,q_k\) the colors in the order of their first occurrence in \(a\), then the first occurrences of these colors in \(b'\) (say at positions \(j_1, j_2, \dots, j_k\) respectively) satisfy \[ j_1 < j_2 < \cdots < j_k. \]

If no valid sequence \(b'\) can be obtained, output -1.

Input Format: The input begins with three integers \(n\), \(m\) and \(k\). The next line contains \(n\) integers \(a_1, a_2, \dots, a_n\). The following line contains \(m\) integers \(b_1, b_2, \dots, b_m\).

Output Format: Output a single integer: the minimum number of modifications required, or -1 if it is impossible to obtain a valid \(b'\) satisfying the conditions.

Example:

For example, consider
\(n=3,\, m=4,\, k=3,\, a=\{1,2,3\}\) and \(b=\{1,3,2,2\}\). Although one might first consider \(b' = \{1,3,2,2\}\), its first occurrences are at positions 1, 2, 3 giving the order \(1,3,2\), which does not match the order \(1,2,3\) from \(a\), so the segments intersect. However, modifying \(b\) into \(b' = \{1,2,3,3\}\) yields first occurrences at positions 1,2,3 in the order \(1,2,3\) (and the extra element does not affect the property), satisfying the conditions. The minimum number of modifications in this case is the minimum edit distance required to achieve such a sequence.

inputFormat

The first line contains three integers \(n\), \(m\) and \(k\).
The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\).
The third line contains \(m\) integers: \(b_1, b_2, \dots, b_m\).

It is guaranteed that \(a\) contains all colors from \(1\) to \(k\) at least once, and each \(b_i\) is one of \(1,2,\dots,k\).

outputFormat

Output a single integer representing the minimum number of modifications needed. If it is impossible to obtain a valid sequence \(b'\), output -1.

sample

3 4 3
1 2 3
1 3 2 2

2