Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Physical Education

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya is a school PE teacher. Unlike other PE teachers, Vasya doesn't like it when the students stand in line according to their height. Instead, he demands that the children stand in the following order: *a*_{1}, *a*_{2}, ..., *a*_{n}, where *a*_{i} is the height of the *i*-th student in the line and *n* is the number of students in the line. The children find it hard to keep in mind this strange arrangement, and today they formed the line in the following order: *b*_{1}, *b*_{2}, ..., *b*_{n}, which upset Vasya immensely. Now Vasya wants to rearrange the children so that the resulting order is like this: *a*_{1}, *a*_{2}, ..., *a*_{n}. During each move Vasya can swap two people who stand next to each other in the line. Help Vasya, find the sequence of swaps leading to the arrangement Vasya needs. It is not required to minimize the number of moves.

Input

The first line contains an integer *n* (1 ≤ *n* ≤ 300) which is the number of students. The second line contains *n* space-separated integers *a*_{i} (1 ≤ *a*_{i} ≤ 10^{9}) which represent the height of the student occupying the *i*-th place must possess. The third line contains *n* space-separated integers *b*_{i} (1 ≤ *b*_{i} ≤ 10^{9}) which represent the height of the student occupying the *i*-th place in the initial arrangement. It is possible that some students possess similar heights. It is guaranteed that it is possible to arrange the children in the required order, i.e. *a* and *b* coincide as multisets.

Output

In the first line print an integer *k* (0 ≤ *k* ≤ 10^{6}) which is the number of moves. It is not required to minimize *k* but it must not exceed 10^{6}. Then print *k* lines each containing two space-separated integers. Line *p*_{i}, *p*_{i} + 1 (1 ≤ *p*_{i} ≤ *n* - 1) means that Vasya should swap students occupying places *p*_{i} and *p*_{i + 1}.

Examples

Input

4

1 2 3 2

3 2 1 2

Output

4

2 3

1 2

3 4

2 3

Input

2

1 100500

1 100500

Output

0

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/01/2020 12:30:25 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|