Japanese parking garages P33845

In the cities of Japan you can see parking garages of every imaginable kind. Unfortunately, during his visit to Japan, the author of this problem was unable to fully understand how they work. So here we will use two simplified models: Q-garages and S-garages.

A Q-garage stores the cars into queues (containers that use the “first in, first out” principle). Only after all the incoming cars have been stored into the queues of a Q-garage, the cars can start leaving the queues. An S-garage is identical to a Q-garage, except that it uses stacks (containers with the “last in, first out” principle) instead of queues.

Suppose that n cars, numbered 1, …, n, arrive at a garage in the order i₁, …, i_n, and must leave it in the order o₁, …, o_n. Which is the minimum number of queues for a Q-garage? And the minimum number of stacks for an S-garage?

For example, assume n = 8, that the incoming order is 6 8 5 2 1 7 3 4, and that the outcoming order must be 2 5 4 7 1 6 8 3. In this case, a Q-garage needs 4 queues, while an S-garage only needs 3 stacks. These are possible (not unique) solutions:

Input

Input consists of several cases. Every case begins with n, where 1 ≤ n ≤ 10⁶, followed by the permutation i₁, …, i_n and the permutation o₁, …, o_n. A single 0 ends the input.

Output

For every case, print its case number, followed by the minimum number of queues for a Q-garage and the minimum number of stacks for an S-garage.