Giải bài trực tuyến

Flowers

There is a traditional game in Vietnam as following:
We have a tower built from N blocks of different colors: red, purple, yellow, blue, etc.
Now we have to disassemble the tower and arrange it into a flower. The flower is of regular-polygonal shape in which their petals are the tower's blocks (see the below figure).

To make the flower, we are allowed to do the following operations:

• Take the top block from the tower and put it into a basket.
• Among the blocks in the baskets, choose one and put it on the left or right of the flower's petals that we have already arranged.
• Take the top block from the tower and, instead of put it into a basket, put it directly on the left or right of the flower's petals that we have already arranged.

Our score is equal to the number of baskets we have to use. Find the minimum score that we can achieve.
Note : After take a block from a basket, we can use this basket to keep other blocks as well. Each basket cannot contain more than one block.

Example

Line 1 : a positive integer N.
Line 2 : N integers representing the colors of the blocks ( from top to bottom ).
Line 3 : N integers respresenting the colors of the flower's petals ( in clockwise order ).

Output

The minimum number of baskets that we need to use. It is guaranteed that we can always arrange such a flower.

Constraints

• N ≤ 1000.
• The blocks' colors are not larger than N.

Example

Input
5
2 1 2 3 4
2 3 1 4 2

Output
1

Output details : First, we take block 2 and put it in bottom position ( see the figure ). Then we take block 1 and put it into a basket ( since we cannot put it on the left or right of block 2 ). Then we take the second block 2 and put it on the right of the first block 2. After that, we take block 3 and put it on the right of block 2. Then we take block 1 (from the basket) and put it on the right of block 3 or take block 4 and put it on the left of block 2. Finally, we put the last block in the last position to complete our flower.