Madeline has an array a of n integers. A pair (u, v) of integers forms an inversion in a if:

  * 1 ≤ u < v ≤ n. 
  * a_u > a_v. 



Madeline recently found a magical paper, which allows her to write two indices u and v and swap the values a_u and a_v. Being bored, she decided to write a list of pairs (u_i, v_i) with the following conditions:

  * all the pairs in the list are distinct and form an inversion in a. 
  * all the pairs that form an inversion in a are in the list. 
  * Starting from the given array, if you swap the values at indices u_1 and v_1, then the values at indices u_2 and v_2 and so on, then after all pairs are processed, the array a will be sorted in non-decreasing order. 



Construct such a list or determine that no such list exists. If there are multiple possible answers, you may find any of them.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 1000) — the length of the array.

Next line contains n integers a_1,a_2,...,a_n (1 ≤ a_i ≤ 10^9) — elements of the array.

Output

Print -1 if no such list exists. Otherwise in the first line you should print a single integer m (0 ≤ m ≤ (n(n-1))/(2)) — number of pairs in the list.

The i-th of the following m lines should contain two integers u_i, v_i (1 ≤ u_i < v_i≤ n).

If there are multiple possible answers, you may find any of them.

Examples

Input


3
3 1 2


Output


2
1 3
1 2


Input


4
1 8 1 6


Output


2
2 4
2 3


Input


5
1 1 1 2 2


Output


0

Note

In the first sample test case the array will change in this order [3,1,2] → [2,1,3] → [1,2,3].

In the second sample test case it will be [1,8,1,6] → [1,6,1,8] → [1,1,6,8].

In the third sample test case the array is already sorted.
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> mass1(n);
  vector<int> p(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    mass1[i] = a[i];
  }
  sort(mass1.begin(), mass1.end());
  for (int i = 0; i < n; i++) {
    a[i] = lower_bound(mass1.begin(), mass1.end(), a[i]) - mass1.begin();
  }
  vector<pair<int, int> > mass2;
  for (int i = 0; i < n; i++) {
    mass2.push_back({a[i], i});
  }
  sort(mass2.begin(), mass2.end());
  vector<pair<int, int> > ans;
  for (int i = n - 1; i >= 0; i--) {
    int j = i;
    while (j >= 0 && mass2[j].first == mass2[i].first) {
      j--;
    }
    j++;
    for (int k = j; k <= i; k++) {
      int ind = mass2[k].second;
      int ind1 = mass2[k].second;
      for (int d = i + 1; d < n; d++) {
        if (d == i + 1 && mass2[d].second < ind) {
          mass2[k].second = mass2[d].second;
        }
        if (mass2[d].second > ind) {
          continue;
        }
        ans.push_back({mass2[d].second, ind});
        if (d == n - 1 || mass2[d + 1].second > ind) {
          mass2[d].second = ind;
        } else {
          mass2[d].second = mass2[d + 1].second;
        }
      }
    }
    i = j;
  }
  for (int i = 0; i < n - 1; i++) {
    if (mass2[i + 1].second < mass2[i].second &&
        mass2[i + 1].first > mass2[i].first) {
      cout << -1;
      return 0;
    }
  }
  cout << ans.size() << "\n";
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i].first + 1 << " " << ans[i].second + 1 << "\n";
  }
  return 0;
}
