Problem Description

You are given two arrays $a, b$ of length $n$. Merge them to obtain an array $c$ of length $2 \times n$.

Let the $i$-th element of array $a$ be placed at position $lb_i$ in array $c$ after merging, and the $i$-th element of array $b$ be placed at position $lc_i$ in array $c$ after merging. After merging, it must satisfy $lb_1 < lb_2 < \dots < lb_{n-1} < lb_n$ and $lc_1 < lc_2 < \dots < lc_{n-1} < lc_n$, meaning the relative order of elements within each array remains unchanged.

After merging, you need to perform the following operations on array $c$:

1. Toggle operation: Choose an interval $[l, r]$. For each $i \in [l, r]$, if $c_i$ equals $y$, change it to a number different from $y$; otherwise, change it to $y$.
2. Reverse operation: Choose an interval $[l, r]$ and reverse the numbers in this subarray. This operation must be performed exactly $z$ times.

Output the minimum number of toggle operations needed to make all numbers in array $c$ equal to $y$.

Input Format

The first line contains three integers $n, y, z$.

The second line contains $n$ integers, representing the elements in array $a$.

The third line contains $n$ integers, representing the elements in array $b$.

Output Format

One positive integer, representing the answer.

5 1 1
1 1 45 1 4
1 9 1 9 810

1

20 0 3
1 0 0 8 6 10 0 8 6 1 0 0 86 1 0 0 8 6 0 0
5 2 0 1 3 1 4 52 0 13 14 0 1 0 1 0 4 0 5 0

4

3 2 4
110 105 117
99 108 98

1

Hint

[Sample Explanation]

For sample $1$, let $c$ be $\{1, 1, 1, 9, 45, 1, 1, 9, 4, 810\}$.

Here, $c_1 = a_1, c_2 = b_1, c_3 = a_2, c_4 = b_2, c_5 = a_3, c_6 = a_4, c_7 = b_3, c_8 = b_4, c_9 = a_5, c_{10} = b_5$. This satisfies the requirements.

Then reverse the interval $[4, 7]$, and array $c$ becomes $\{1, 1, 1, 1, 1, 45, 9, 9, 4, 810\}$.

Next, perform a toggle operation to change all numbers in $[6, 10]$ into $1$.

So only one toggle operation is needed at minimum. It can be proven that no strategy is better than this.

[Constraints]

Please note the special time limit of this problem and use faster I/O.

This problem uses bundled testdata.

Special Property A: It is guaranteed that the elements in the two arrays are either all equal to $y$, or all not equal to $y$.

For all testdata, it is guaranteed that $0 \leqslant y, z \leqslant 10^9$, and all input data are within the int range.

Translated by ChatGPT 5