#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
const long double EPSILON = 0.000000001;
const long long int mod = 1e9 + 7;
const long long int AM = 2e5 + 5;
const long double pi = 3.14159265358979323846;
long long int max(long long int a, long long int b) {
  if (a > b)
    return a;
  else
    return b;
}
using namespace std;
long long int fact(long long int n) {
  long long int ans = 1;
  for (long long int i = 1; i <= n; i++) ans *= i;
  return ans;
}
long long int powm(long long int a, long long int b, long long int n) {
  long long int x = 1, y = a;
  while (b > 0) {
    if (b % 2 == 1) {
      x = (x * y) % n;
    }
    y = (y * y) % n;
    b /= 2;
  }
  return x % n;
}
long long int pow(long long int x, long long int y) {
  long long int res = 1;
  while (y > 0) {
    if (y & 1) res = ((res) * (x));
    y = y >> 1;
    x = ((x) * (x));
  }
  return res;
}
long long int min(long long int a, long long int b) {
  if (a > b)
    return b;
  else
    return a;
}
bool cmp(long double x, long double y) {
  if (abs(x - y) <= EPSILON) return 1;
  return 0;
}
bool checkprime(long long int n) {
  for (long long int i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int lcm(long long int a, long long int b) {
  return (a * b) / gcd(a, b);
}
long long int modInverse(long long int a, long long int m) {
  long long int g = gcd(a, m);
  return powm(a, m - 2, m);
}
vector<long long int> a, b;
vector<pair<int, int>> ans;
void print(int l, int r) {
  for (int i = r; i > l; i--) {
    swap(b[i - 1], b[i]);
    ans.push_back({i, i + 1});
  }
}
int main() {
  int n;
  cin >> n;
  a.resize(n);
  b.resize(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  for (int i = 0; i < n; i++) {
    if (a[i] != b[i]) {
      for (int j = i + 1; j < n; j++) {
        if (b[j] == a[i]) {
          print(i, j);
          break;
        }
      }
    }
  }
  cout << ans.size() << "\n";
  for (auto [l, r] : ans) cout << l << " " << r << "\n";
  return 0;
}

### Prompt

Create a solution in CPP for the following problem:

Vasya 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: a1, a2, ..., an, where ai 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: b1, b2, ..., bn, which upset Vasya immensely. Now Vasya wants to rearrange the children so that the resulting order is like this: a1, a2, ..., an. 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 ai (1 ≤ ai ≤ 109) which represent the height of the student occupying the i-th place must possess. The third line contains n space-separated integers bi (1 ≤ bi ≤ 109) 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 ≤ 106) which is the number of moves. It is not required to minimize k but it must not exceed 106. Then print k lines each containing two space-separated integers. Line pi, pi + 1 (1 ≤ pi ≤ n - 1) means that Vasya should swap students occupying places pi and pi + 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

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
const long double EPSILON = 0.000000001;
const long long int mod = 1e9 + 7;
const long long int AM = 2e5 + 5;
const long double pi = 3.14159265358979323846;
long long int max(long long int a, long long int b) {
  if (a > b)
    return a;
  else
    return b;
}
using namespace std;
long long int fact(long long int n) {
  long long int ans = 1;
  for (long long int i = 1; i <= n; i++) ans *= i;
  return ans;
}
long long int powm(long long int a, long long int b, long long int n) {
  long long int x = 1, y = a;
  while (b > 0) {
    if (b % 2 == 1) {
      x = (x * y) % n;
    }
    y = (y * y) % n;
    b /= 2;
  }
  return x % n;
}
long long int pow(long long int x, long long int y) {
  long long int res = 1;
  while (y > 0) {
    if (y & 1) res = ((res) * (x));
    y = y >> 1;
    x = ((x) * (x));
  }
  return res;
}
long long int min(long long int a, long long int b) {
  if (a > b)
    return b;
  else
    return a;
}
bool cmp(long double x, long double y) {
  if (abs(x - y) <= EPSILON) return 1;
  return 0;
}
bool checkprime(long long int n) {
  for (long long int i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
long long int gcd(long long int a, long long int b) {
  return b ? gcd(b, a % b) : a;
}
long long int lcm(long long int a, long long int b) {
  return (a * b) / gcd(a, b);
}
long long int modInverse(long long int a, long long int m) {
  long long int g = gcd(a, m);
  return powm(a, m - 2, m);
}
vector<long long int> a, b;
vector<pair<int, int>> ans;
void print(int l, int r) {
  for (int i = r; i > l; i--) {
    swap(b[i - 1], b[i]);
    ans.push_back({i, i + 1});
  }
}
int main() {
  int n;
  cin >> n;
  a.resize(n);
  b.resize(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) cin >> b[i];
  for (int i = 0; i < n; i++) {
    if (a[i] != b[i]) {
      for (int j = i + 1; j < n; j++) {
        if (b[j] == a[i]) {
          print(i, j);
          break;
        }
      }
    }
  }
  cout << ans.size() << "\n";
  for (auto [l, r] : ans) cout << l << " " << r << "\n";
  return 0;
}

```