Camila, like many young Filipinos, is a girl in love. She has fallen hopelessly in love with Shawn, her upperclassman in their Programming Club who always helps her debug her code. She wishes that she could pretend she didn't need him, but she knows that he overhears her complaining about her loops not terminating at the right times. "It's true," she lalala-ed. "It should be running."
She doesn't think Shawn even knows her name, since every time they talk, he calls her "señorita." That's perfectly fine with her, since she loves it when he calls her señorita. Thus, to win over his heart, she needs to plan out the perfect outfit for each of the next few days, so she can keep hearing him call her señorita.
She has two stacks of shirts in her cabinet, one with $m$ shirts and the other with $n$ shirts. She is going to wear each of these shirts exactly once over the course of the next $m + n$ days, and each shirt has been assigned a number from $1$ to $m + n$ to indicate on what day she wants to wear it.
On day $i$, Camila wants to wear shirt $i$ from her cabinet. Unfortunately, the shirt that she needs for the day might not be on top, and could be buried under the other shirts. Since her shirts are organized into stacks, Camila only has two operations available to her:
She asked her mom if she could arrange her clothes differently, but her mom just replied, "Well, _señorita_, if you have the energy to complain about the way I do the laundry, maybe you have the energy to do it yourself, then!" Camila decided she doesn't enjoy it as much when it is her mom who calls her señorita. Regardless, her mom is right in that Camila is very lazy, and doesn't want to expend more energy than is necessary in retrieving her shirts.
Given the initial ordering of her shirts, what is the minimum amount of energy that Camila will have to expend in total in order to be able to wear the correct shirt on each of the next $m + n$ days, and have Shawn call her señorita?
Input consists of two lines. The first line begins with a single integer $m$. Then if $m > 0$, this is followed by a space, then $m$ space-separated integers. Similarly, the second line begins with a single integer $n$. Then, if $n > 0$, this is followed by a space, then $n$ space-separated integers. These represent the two stacks of clothes, with $m$ and $n$ shirts in each stack, respectively, and with the integers themselves representing the day when Camila wishes to wear each shirt. These integers are given in the order the shirts appear in the stack, with the first integer representing the shirt at the *bottom* of that stack, and the last integer of each line representing the shirt at the *top* of that stack.
Each of the integers from $1$ to $m + n$ is guaranteed to appear exactly once among the integers in the stacks.
Output one line containing the minimum amount of energy that Camila must expend.
$0 <= m, n$
$1 <= m + n <= 4 times 10^5$
*Subtask 1* (30 pts):
$1 <= m + n <= 4000$
*Subtask 2* (1 point):
For each stack, if $i < j$, then shirt $i$ is on top of shirt $j$.
*Subtask 3* (19 points):
For each stack, if $i < j$, then shirt $i$ is underneath shirt $j$.
*Subtask 4* (50 points):
No further restrictions.
First, to retrieve shirt 1, Camila moves shirt 3 and shirt 5 to the other stack, expending 2 units of energy. Then, she can remove shirt 1 from the stacks.
Now, Camila has to retrieve shirt 2. To do this, she moves shirts 5, then 3, then 4, then 6, which are on top of shirt 2, onto the other stack. This costs 4 units of energy. Then, she can remove shirt 2 from the stacks.
Next, Camila has to retrieve shirt 3. To do this, she moves shirt 6 then shirt 4 over to the other stack, expending 2 units of energy. Then, she can remove shirt 3 from the stacks.
From this position, we can show that Camila can retrieve the remainder of her shirts without expending any more energy. We can also show that this series of moves is optimal for minimizing the amount of energy spent. Thus, Camila must spend $2 + 4 + 2 = 8$ units of energy in total.
## Input
Input consists of two lines. The first line begins with a single integer $m$. Then if $m > 0$, this is followed by a space, then $m$ space-separated integers. Similarly, the second line begins with a single integer $n$. Then, if $n > 0$, this is followed by a space, then $n$ space-separated integers. These represent the two stacks of clothes, with $m$ and $n$ shirts in each stack, respectively, and with the integers themselves representing the day when Camila wishes to wear each shirt. These integers are given in the order the shirts appear in the stack, with the first integer representing the shirt at the *bottom* of that stack, and the last integer of each line representing the shirt at the *top* of that stack.Each of the integers from $1$ to $m + n$ is guaranteed to appear exactly once among the integers in the stacks.
## Output
Output one line containing the minimum amount of energy that Camila must expend.
[samples]
## Scoring
$0 <= m, n$$1 <= m + n <= 4 times 10^5$*Subtask 1* (30 pts):$1 <= m + n <= 4000$*Subtask 2* (1 point):For each stack, if $i < j$, then shirt $i$ is on top of shirt $j$.*Subtask 3* (19 points):For each stack, if $i < j$, then shirt $i$ is underneath shirt $j$.*Subtask 4* (50 points):No further restrictions.
## Note
First, to retrieve shirt 1, Camila moves shirt 3 and shirt 5 to the other stack, expending 2 units of energy. Then, she can remove shirt 1 from the stacks.Now, Camila has to retrieve shirt 2. To do this, she moves shirts 5, then 3, then 4, then 6, which are on top of shirt 2, onto the other stack. This costs 4 units of energy. Then, she can remove shirt 2 from the stacks.Next, Camila has to retrieve shirt 3. To do this, she moves shirt 6 then shirt 4 over to the other stack, expending 2 units of energy. Then, she can remove shirt 3 from the stacks.From this position, we can show that Camila can retrieve the remainder of her shirts without expending any more energy. We can also show that this series of moves is optimal for minimizing the amount of energy spent. Thus, Camila must spend $2 + 4 + 2 = 8$ units of energy in total.
**Definitions**
Let $ m, n \in \mathbb{Z}_{\geq 0} $ be the sizes of two stacks.
Let $ A = (a_1, a_2, \dots, a_m) $ be the first stack, where $ a_1 $ is the bottom and $ a_m $ is the top.
Let $ B = (b_1, b_2, \dots, b_n) $ be the second stack, where $ b_1 $ is the bottom and $ b_n $ is the top.
Let $ S = \{1, 2, \dots, m+n\} $ be the set of shirt labels, each corresponding to the day it must be worn.
Define a permutation $ \pi: \{1, \dots, m+n\} \to S $ such that $ \pi(i) $ is the shirt on top of the stack at step $ i $, and the goal is to retrieve shirts in increasing order $ 1, 2, \dots, m+n $.
**Constraints**
1. Each integer from $ 1 $ to $ m+n $ appears exactly once in $ A \cup B $.
2. At each step $ i $, to retrieve shirt $ i $, all shirts above it in its current stack must be moved to the other stack (each move costs 1 unit of energy).
3. After removal, the shirt is discarded; the remaining shirts stay in their stacks.
4. The only allowed operations are moving the top shirt from one stack to the top of the other stack, or removing the top shirt if it is the desired one.
**Objective**
Minimize the total energy (number of moves) required to retrieve shirts $ 1, 2, \dots, m+n $ in order.
Let $ \text{pos}(x) $ denote the position (stack and index) of shirt $ x $ in the initial configuration.
Let $ \text{top}(A) $ and $ \text{top}(B) $ denote the current top shirts of stacks $ A $ and $ B $.
At step $ i $, if shirt $ i $ is not on top of either stack, move all shirts above it (in its stack) to the other stack, one by one, costing $ k $ energy where $ k $ is the number of shirts above it.
If shirt $ i $ is on top of a stack, remove it at no extra cost beyond the moves already made to expose it.
The minimal total energy is the sum over $ i = 1 $ to $ m+n $ of the number of shirts that must be moved from the stack containing shirt $ i $ to expose it, **excluding** shirts already moved in prior steps.
**Optimization Insight**:
Use a greedy simulation with two stacks and a pointer for the next required shirt. Maintain a data structure (e.g., a set or array) to track which shirts are still in the stacks. For each $ i $, determine which stack contains $ i $, count how many shirts above it remain (i.e., have not been removed yet), and move them to the other stack. The total moves is the answer.
Formally, the minimal energy is:
$$
\sum_{i=1}^{m+n} \left( \text{number of shirts above } i \text{ in its stack at step } i \right)
$$
where "above" means closer to the top and not yet removed.
This can be computed efficiently using a simulation with two deques or lists, tracking the current state of each stack and the removal order.