Back to School '17: Sour Candy

View as PDF

Submit solution


Points:15 (partial)
Time limit:3.0s
Memory limit:256M
Authors:

Problem type

One summer day, April bought N pieces of sour candy to eat. Each piece of candy has a unique sourness value s_{n} 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.

Input Specification

The first line contains an integer N, which is the amount of sour candy April has.

The next line contains a sequence of N space separated integers s_{n}, where s_{n} indicates the sourness of the n^{th} candy.

The final line contains N space separated integers, representing the new order April wants to place her candy in.

Constraints

Subtask 1 [10%]

1 \le N \le 10

Subtask 2 [30%]

1 \le N \le 10^3

Subtask 3 [60%]

1 \le N \le 10^5

For all subtasks, 1 \le s_{n} \le 10^9.

Output Specification

On the first line, output a single integer S, representing the minimum number of moves it takes for April to arrange her sour candy.

On the next S lines, output the instructions followed to arrange the sour candy. Output F i to move the i^\text{th} element (1-indexed) to the front and B i to move the i^\text{th} 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 5 to the front of the lineup. She can then move the candy with sourness value 1 to the back of the line. Note that the candy with sourness value 1 was shifted to index 2 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 3 to the front, then move the candy with sourness value 5 to the front.


Report an issue

Comments