Back to School '17: Sour CandyView as PDF
One summer day, April bought pieces of sour candy to eat. Each piece of candy has a unique sourness value which indicates how sour it is.
Initially, the candy pieces were lined up in a straight line. However, April wants to change the order of the candies by taking any piece of candy, and placing it either at the front or back of the line. Given the order April wants to place the candies in, find the minimum number of moves needed to place them in that arrangement.
The first line contains an integer , which is the amount of sour candy April has.
The next line contains a sequence of space separated integers , where indicates the sourness of the candy.
The final line contains space separated integers, representing the new order April wants to place her candy in.
Subtask 1 [10%]
Subtask 2 [30%]
Subtask 3 [60%]
For all subtasks, .
On the first line, output a single integer , representing the minimum number of moves it takes for April to arrange her sour candy.
On the next lines, output the instructions followed to arrange the sour candy. Output
F i to move the element (1-indexed) to the front and
B i to move the element to the back.
If there are multiple possible ordering of operations you may output any of them. It is guaranteed that it is always possible to rearrange the candy.
Sample Input 1
5 1 2 3 4 5 5 2 3 4 1
Sample Output 1
2 F 5 B 2
Explanation for Sample Output 1
April can move the candy with sourness value to the front of the lineup. She can then move the candy with sourness value to the back of the line. Note that the candy with sourness value was shifted to index before being moved.
The only other solution is
2 B 1 F 4
Sample Input 2
4 4 3 5 2 5 3 4 2
Sample Output 2
2 F 2 F 3
Explanation for Sample Output 2
April can move the candy with sourness value to the front, then move the candy with sourness value to the front.