You are given an array with 2n numbers; each number between 1\dots n occurs exactly twice. Your task is to sort the array so that each pair of duplicates occurs next to each other. The only operation you can use is swapping any two elements (not necessarily adjacent).

Show how to do sorting with at most n-1 swaps.

Input

The first input line has one integer n. The second line has 2n numbers: the contents of the array.

Output

First print an integer k: the number of swaps

Then, print k lines that describe the swaps. You can print any valid solution.

Constraints

• 1 \le n \le 10^5

Example 1

Input:

3
1 2 1 3 2 3

Output:

2
1 5
3 6

Explanation:

You start with:

1 2 1 3 2 3

You swap elements in positions 1 and 5 to get:

2 2 1 3 1 3

Then you swap elements in positions 3 and 6 to get:

2 2 3 3 1 1

And now you are done.