A Permutation Problem

Limits: 2 sec., 512 MiB

You have a permutation of \(n\) integers from 1 to \(n\), inclusive. Your task is to sort the permutation, and you have to swap each pair of integers exactly one. Can you do that?

Input

The first line contains a single integer \(n\). The second line contains intersection \(a\) of integers between \(1\) and \(n\).

Output

Print no if it’s impossible to sort the permutation. Otherwise print \(n*(n-1)/2\) lines that describe the pairs of of number to swap on the corresponsing turn.

Constraints

\(2 \leq n \leq 1000\).

Samples