406716: GYM102503 M Señorita

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:

• Camila can take the top shirt of one stack and move it to the top of the other stack. This takes $$$1$$$ unit of energy.
• If the desired shirt $$$i$$$ is on top of either of the stacks, Camila takes it and wears it for the day. This does not cost any energy. The shirt is then thrown into the laundry, and thus permanently removed from the stack (since Camila does not do her own laundry).

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 \le m, n $$$

$$$1 \le m+n \le 4 \times 10^5$$$

Subtask 1 (30 pts):

$$$1 \le m+n \le 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.

3 1 5 3
4 7 2 6 4

8

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.