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*_{1}, …, *i*_{n},
and must leave it in the order *o*_{1}, …, *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^{6},
followed by the permutation *i*_{1}, …, *i*_{n}
and the permutation *o*_{1}, …, *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.

Public test cases

**Input**

8 1 2 3 4 5 6 7 8 4 3 8 6 5 1 2 7 1 1 1 9 5 2 9 6 1 7 4 3 8 2 6 7 3 5 9 1 4 8 10 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1 0

**Output**

Case 1: 4 3 Case 2: 1 1 Case 3: 2 5 Case 4: 10 1

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Cinquè Concurs de Programació de la UPC - Final
- Date
- 2007-10-03