Problem: In this problem your goal is to sort an array consisting of n integers in at most n swaps. For the given array find the sequence of swaps that makes the array sorted in the non-descending order. Swaps are performed consecutively, one after another.

Note that in this problem you do not have to minimize the number of swaps — your task is to find any sequence that is no longer than n.

Input

The first line of the input contains integer n (1 ≤ n ≤ 3000) — the number of array elements. The second line contains elements of array: a0, a1, ..., an - 1 ( - 109 ≤ ai ≤ 109), where ai is the i-th element of the array. The elements are numerated from 0 to n - 1 from left to right. Some integers may appear in the array more than once.

Output

In the first line print k (0 ≤ k ≤ n) — the number of swaps. Next k lines must contain the descriptions of the k swaps, one per line. Each swap should be printed as a pair of integers i, j (0 ≤ i, j ≤ n - 1), representing the swap of elements ai and aj. You can print indices in the pairs in any order. The swaps are performed in the order they appear in the output, from the first to the last. It is allowed to print i = j and swap the same pair of elements multiple times.

If there are multiple answers, print any of them. It is guaranteed that at least one answer exists.

Examples

Input

5
5 2 5 1 4


Output

2
0 3
4 2


Input

6
10 20 20 40 60 60


Output

0


Input

2
101 100


Output

1
0 1

Solution (in JAVA):

Solution:
//################################################################################################################
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.io.Writer;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.List;

//################################################################################################################
public class R2775D2A {
	public static void main(String[] args) {
		R2775D2A a = new R2775D2A();
		InputReader1 reader = a.new InputReader1(System.in);
		OutputWriter writer = a.new OutputWriter(System.out);
		// put your code here
		int n = reader.readInt();
		int[] arr = new int[n];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = reader.readInt();
		}
		List<String> swaps = new ArrayList<String>();
		for (int i = 0; i < arr.length; i++) {
			int mn = arr[i];
			int mni = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < mn) {
					mn = arr[j];
					mni = j;
				}
			}
			if (mni != i) {
				int tmp = arr[i];
				arr[i] = arr[mni];
				arr[mni] = tmp;
				swaps.add(i + " " + mni);
			}
		}
		writer.println(swaps.size());
		for (int i = 0; i < swaps.size(); i++) {
			writer.println(swaps.get(i));
		}
		reader.close();
		writer.close();
	}

	class InputReader1 {
		// private final boolean finished = false;

		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader1(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int peek() {
			if (numChars == -1)
				return -1;
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					return -1;
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar];
		}

		public int readInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long readLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String readString() {
			int length = readInt();
			if (length < 0)
				return null;
			byte[] bytes = new byte[length];
			for (int i = 0; i < length; i++)
				bytes[i] = (byte) read();
			try {
				return new String(bytes, "UTF-8");
			} catch (UnsupportedEncodingException e) {
				return new String(bytes);
			}
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private String readLine0() {
			StringBuffer buf = new StringBuffer();
			int c = read();
			while (c != '\n' && c != -1) {
				if (c != '\r')
					buf.appendCodePoint(c);
				c = read();
			}
			return buf.toString();
		}

		public String readLine() {
			String s = readLine0();
			while (s.trim().length() == 0)
				s = readLine0();
			return s;
		}

		public String readLine(boolean ignoreEmptyLines) {
			if (ignoreEmptyLines)
				return readLine();
			else
				return readLine0();
		}

		public BigInteger readBigInteger() {
			try {
				return new BigInteger(readString());
			} catch (NumberFormatException e) {
				throw new InputMismatchException();
			}
		}

		public char readCharacter() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			return (char) c;
		}

		public double readDouble() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') {
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, readInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') {
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) {
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, readInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}

		public boolean isExhausted() {
			int value;
			while (isSpaceChar(value = peek()) && value != -1)
				read();
			return value == -1;
		}

		public String next() {
			return readString();
		}

		public boolean readBoolean() {
			return readInt() == 1;
		}

		public void close() {
			try {
				stream.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}

	class OutputWriter {
		private final PrintWriter writer;

		public OutputWriter(OutputStream stream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(
					stream)));
		}

		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}

		public void println(String s) {
			writer.println(s);
		}

		public void println(int x) {
			writer.println(x);
		}

		public void print(int x) {
			writer.print(x);
		}

		public void println(long x) {
			writer.println(x);
		}

		public void printSpace() {
			writer.print(" ");
		}

		public void close() {
			writer.close();
		}
	}
}