Problem: You are given a permutation p of integers from 1 to n, where n is an even number. 

Your goal is to sort the permutation. To do so, you can perform zero or more operations of the following type: 

  * take two indices i and j such that 2 ⋅ |i - j| ≥ n and swap p_i and p_j. 



There is no need to minimize the number of operations, however you should use no more than 5 ⋅ n operations. One can show that it is always possible to do that.

Input

The first line contains a single integer n (2 ≤ n ≤ 3 ⋅ 10^5, n is even) — the length of the permutation. 

The second line contains n distinct integers p_1, p_2, …, p_n (1 ≤ p_i ≤ n) — the given permutation.

Output

On the first line print m (0 ≤ m ≤ 5 ⋅ n) — the number of swaps to perform.

Each of the following m lines should contain integers a_i, b_i (1 ≤ a_i, b_i ≤ n, |a_i - b_i| ≥ n/2) — the indices that should be swapped in the corresponding swap.

Note that there is no need to minimize the number of operations. We can show that an answer always exists.

Examples

Input


2
2 1


Output


1
1 2

Input


4
3 4 1 2


Output


4
1 4
1 4
1 3
2 4


Input


6
2 5 3 1 4 6


Output


3
1 5
2 5
1 4

Note

In the first example, when one swap elements on positions 1 and 2, the array becomes sorted.

In the second example, pay attention that there is no need to minimize number of swaps.

In the third example, after swapping elements on positions 1 and 5 the array becomes: [4, 5, 3, 1, 2, 6]. After swapping elements on positions 2 and 5 the array becomes [4, 2, 3, 1, 5, 6] and finally after swapping elements on positions 1 and 4 the array becomes sorted: [1, 2, 3, 4, 5, 6].

Solution (in JAVA):

Solution:
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

public class Codeforces {

    static double Phi = (1 + Math.sqrt(5)) / 2.0;
    static int MAX = -1 >>> 1;
    static long MODL = 1_000_000_007L;
    static int MOD = 1_000_000_007;
    static void no() throws IOException {println("NO");}
    static void yes() throws IOException {println("YES");}

    static boolean testCases = false;
    static boolean DEBUG = false;

    static List<String> swappings;
    static void main() throws Exception {
        int n = ni();
        int[] p = new int[1 + n];
        for (int i = 1; i <= n; ++i) {
            p[i] = ni();
        }
        int lf = n >> 1;
        int gap = n >> 1;

        swappings = new ArrayList<>();
        for (int i = lf; i >= 1; ) {
            if (p[i] <= lf) {
                --i;
                continue;
            }
            if (p[i] - i >= gap) {
                swap(p, i, p[i]);
            } else {
                int save = p[i];

                swap(p, i, n);
                swap(p, n, 1);
                swap(p, 1, save);
                swap(p, i, n);
            }
        }
        debug("First run thru");
        debug(Arrays.toString(p));
        for (int i = lf; i >= 1;) {
            if (p[i] == i) {
                --i;
                continue;
            }
            int save = p[i];
            swap(p, i, n);
            swap(p, n, save);
            swap(p, i, n);
        }
        debug("Second run");
        debug(Arrays.toString(p));
        for (int i = lf + 1; i <= n;) {
            if (p[i] == i) {
                ++i;
                continue;
            }
            int save = p[i];
            swap(p, i, 1);
            swap(p, 1, save);
            swap(p, i, 1);
        }

        println(swappings.size());
        for (String s : swappings) println(s);
        debug(Arrays.toString(p));
    }
    static void swap(int[] p, int f, int s) {
        // println("swapping indices " + f + "(" + p[f] + ") and " + s + "(" + p[s] + ")");
        swappings.add(f + " " + s);
        int t = p[s];
        p[s] = p[f];
        p[f] = t;
    }
    public static void main(String[] args) throws Exception {
        long startPointTime = System.currentTimeMillis();
        scannerIn = System.in;
        printerBW = new BufferedWriter(new OutputStreamWriter(System.out));
        if (DEBUG && System.getenv("HABLA") != null) {
            HABLA = true;
            debug("Automatic debugging " + System.getenv("HABLA"));
        }

        int t = testCases ? ni() : 1;
        int to = t;
        while (t-- > 0) {
            debug("Case #" + (to - t) + " ---------------- ");
            main();
        }
        long endTime = System.currentTimeMillis();
        float totalProgramTime = endTime - startPointTime;
        if (args.length > 0 && args[0].equalsIgnoreCase("time") || args.length > 1 && args[1].equalsIgnoreCase("time"))
            print("Execution time is " + totalProgramTime + " (" + (totalProgramTime / 1000) + "s)");
        close();
    }
//            /$$
//           | $$
//   /$$$$$$$| $$  /$$$$$$   /$$$$$$$ /$$$$$$$  /$$$$$$   /$$$$$$$
//  /$$_____/| $$ |____  $$ /$$_____//$$_____/ /$$__  $$ /$$_____/
// | $$      | $$  /$$$$$$$|  $$$$$$|  $$$$$$ | $$$$$$$$|  $$$$$$
// | $$      | $$ /$$__  $$ \____  $$\____  $$| $$_____/ \____  $$
// |  $$$$$$$| $$|  $$$$$$$ /$$$$$$$//$$$$$$$/|  $$$$$$$ /$$$$$$$/
//  \_______/|__/ \_______/|_______/|_______/  \_______/|_______/


    static class Pair {
        int x;
        int y;
        Pair(Pair x) {
            this.x = x.x;
            this.y = x.y;
        }
        Pair(int a, int b) {
            this.x = a;
            this.y = b;
        }
        public String toString() {
            return x + "(" + y + ")";
        }
    }
    static class DisjointSet {
        int[] arr;
        int[] size;
        boolean enableSize = true;

        DisjointSet(int n) {
            arr = new int[n + 1];
            this.enableSize = enableSize;
            if (this.enableSize) size = new int[n + 1];
            makeSet();
        }

        void makeSet() {
            for (int i = 1; i < arr.length; i++) {
                arr[i] = i;
                if (enableSize) size[i] = 1;
            }
        }

        void union(int i, int j) {
            i = find(i);
            j = find(j);

            if (i == j)
                return;
            arr[j] = arr[i];
            if (enableSize) {
                size[i] += size[j];
                size[j] = size[i];
            }
        }

        int find(int i) {
            if (i == arr[i]) return i;
            return arr[i] = find(arr[i]);
        }

        int getSize(int i) {
            if (enableSize) return size[find(i)];
            return 0;
        }

        public String toString() {
            return Arrays.toString(arr);
        }
    }

//              /$$     /$$ /$$
//             | $$    |__/| $$
//  /$$   /$$ /$$$$$$   /$$| $$  /$$$$$$$
// | $$  | $$|_  $$_/  | $$| $$ /$$_____/
// | $$  | $$  | $$    | $$| $$|  $$$$$$
// | $$  | $$  | $$ /$$| $$| $$ \____  $$
// |  $$$$$$/  |  $$$$/| $$| $$ /$$$$$$$/
//  \______/    \___/  |__/|__/|_______/

    static int sign(int x) {
        if (x == 0) return 0;
        return x > 0 ? 1 : - 1;
    }

    static long sign(long x) {
        if (x == 0) return 0;
        return x > 0 ? 1 : - 1;
    }

    static int diff(int a, int b) {
        return abs(a - b);
    }

    static long diff(long a, long b) {
        return abs(a - b);
    }

    static boolean isSqrt(double a) {
        double sr = Math.sqrt(a);
        return ((sr - Math.floor(sr)) == 0);
    }

    static long abs(long a) {
        return Math.abs(a);
    }

    static int abs(int a) {
        return Math.abs(a);
    }

    static int min(int ... arr) {
        int min = Integer.MAX_VALUE;
        for (int var : arr)
            min = Math.min(min, var);
        return min;
    }

    static long min(long ... arr) {
        long min = Long.MAX_VALUE;
        for (long var : arr)
            min = Math.min(min, var);
        return min;
    }

    static long max(long ... arr) {
        long max = Long.MIN_VALUE;
        for (long var : arr)
            max = Math.max(max, var);
        return max;
    }

    static int max(int... arr) {
        int max = Integer.MIN_VALUE;
        for (int var : arr)
            max = Math.max(max, var);
        return max;
    }

    static long modInverse(long a) {
        long[] g = gcde(a, MODL);
        long x = g[1], y = g[2];
        if (g[0] != 1)
            return 0;
        else {
            // m is added to handle negative x
            return (g[1] % MODL + MODL) % MODL;
        }
    }

    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static long[] gcde(long a, long b) {
        // Base Case
        if (a == 0) {
            return new long[] {b, 0, 1};
        }

        long[] gcd = gcde(b % a, a);
        long x1 = gcd[1], y1 = gcd[2]; // To store results of recursive call

        // Update x and y using results of recursive
        // call
        gcd[1] = y1 - (b / a) * x1;
        gcd[2] = x1;

        return gcd;
    }

// ____________________________________________________________________________
//|                                                                            |
//|  /$$$$$$  /$$$$$$         /$$$$$$   /$$                /$$$$$$   /$$$$$$   |
//| |_  $$_/ /$$__  $$       /$$__  $$ | $$               /$$__  $$ /$$__  $$  |
//|   | $$  | $$  \ $$      | $$  \__//$$$$$$   /$$   /$$| $$  \__/| $$  \__/  |
//|   | $$  | $$  | $$      |  $$$$$$|_  $$_/  | $$  | $$| $$$$    | $$$$      |
//|   | $$  | $$  | $$       \____  $$ | $$    | $$  | $$| $$_/    | $$_/      |
//|   | $$  | $$  | $$       /$$  \ $$ | $$ /$$| $$  | $$| $$      | $$        |
//|  /$$$$$$|  $$$$$$/      |  $$$$$$/ |  $$$$/|  $$$$$$/| $$      | $$        |
//| |______/ \______/        \______/   \___/   \______/ |__/      |__/        |
//|____________________________________________________________________________|

    private static boolean HABLA = false;

    private static byte[] scannerByteBuffer = new byte[1024]; // Buffer of Bytes
    private static int scannerIndex;
    private static InputStream scannerIn;
    private static int scannerTotal;
    private static BufferedWriter printerBW;

    private static int next() throws IOException { // Scan method used to scan buf
        if (scannerTotal < 0)
            throw new InputMismatchException();
        if (scannerIndex >= scannerTotal) {
            scannerIndex = 0;
            scannerTotal = scannerIn.read(scannerByteBuffer);
            if (scannerTotal <= 0)
                return -1;
        }
        return scannerByteBuffer[scannerIndex++];
    }

    static int ni() throws IOException {
        int integer = 0;
        int n = next();
        while (isWhiteSpace(n)) // Removing startPointing whitespaces
            n = next();
        int neg = 1;
        if (n == '-') { // If Negative Sign encounters
            neg = -1;
            n = next();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = next();
            } else
                throw new InputMismatchException();
        }
        return neg * integer;
    }

    static long nl() throws IOException {
        long integer = 0;
        int n = next();
        while (isWhiteSpace(n)) // Removing startPointing whitespaces
            n = next();
        int neg = 1;
        if (n == '-') { // If Negative Sign encounters
            neg = -1;
            n = next();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = next();
            } else
                throw new InputMismatchException();
        }
        return neg * integer;
    }

    static String line() throws IOException {
        StringBuilder sb = new StringBuilder();
        int n = next();
        while (isWhiteSpace(n))
            n = next();
        while (!isNewLine(n)) {
            sb.append((char) n);
            n = next();
        }
        return sb.toString();
    }

    private static boolean isNewLine(int n) {
        return n == '\n' || n == '\r' || n == -1;
    }

    private static boolean isWhiteSpace(int n) {
        return n == ' ' || isNewLine(n) || n == '\t';
    }

    static int[] nia(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = ni();
        return array;
    }

    static int[][] n2dia(int r, int c) throws Exception {
        if (r < 0 || c < 0)
            throw new Exception("Array size should be non negative");
        int[][] array = new int[r][c];
        for (int i = 0; i < r; i++)
            array[i] = nia(c);
        return array;
    }

    static long[] nla(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        long[] array = new long[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static float[] nfa(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        float[] array = new float[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static double[] nda(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        double[] array = new double[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static <T> void print(T ... str) {
        try {
            for (T ele : str)
                printerBW.append(ele.toString());
            if (DEBUG)
                flush();
        } catch (IOException e) {
            System.out.println(e.toString());
        }
    }

    static <T> void println(T ... str) {
        if (str.length == 0) {
            print('\n');
            return;
        }
        for (T ele : str)
            print(ele, '\n');
    }

    static <T> void debugl(T str) throws IOException {
        if (!DEBUG || !HABLA) return;
        if (str == null) {
            printerBW.append("null");
        } else {
            printerBW.append(str.toString());
        }
        flush();
    }

    static void debug() throws IOException {
        if (!DEBUG || !HABLA) return;
        printerBW.append('\n');
        flush();
    }

    static <T> void debug(T str) throws IOException {
        if (!DEBUG || !HABLA) return;
        if (str == null) {
            printerBW.append("null\n");
        } else {
            printerBW.append(str.toString());
            printerBW.append('\n');
        }
        flush();
    }


    static void flush() throws IOException {
        printerBW.flush();
    }

    static void close() {
        try {
            printerBW.close();
        } catch (IOException e) {
            System.out.println(e.toString());
        }
    }
}