PROGRAMMING:Splay sorting (5)
When Xiao Ming wrote a C language topic, he found that his submitted code ran overtime due to the problem of sorting algorithm. Xiao Ming used bubble algorithm before. After he learned how to play, he planned to sort the input numbers by inserting them into the play in order to shorten the sorting time. At the same time, he could also know how many numbers in the play were less than the number after each number was inserted.
###Input format:
The first line is a positive integer n, starting from the second line is n integers, and the two integers are separated by spaces. 1≤n≤100000。
###Output format:
Output n + 1 rows.
For the first n lines, the i-th line contains two numbers: the i-th input number and the number less than it when inserted.
In the N + 1 line, the given n numbers are output from small to large, separated by spaces, and there is no space at the end of the line.
###Input example:
Here is a set of inputs. For example:
```in
ten
89 2 21 534 12 423 542 35 11 21
```
###Output example:
The corresponding output is given here. For example:
```out
89 0
2 0
21 1
534 3
12 1
423 4
542 6
35 3
11 1
21 3
2 11 12 21 21 35 89 423 534 542
```
answer：If there is no answer, please comment
###Input format:
The first line is a positive integer n, starting from the second line is n integers, and the two integers are separated by spaces. 1≤n≤100000。
###Output format:
Output n + 1 rows.
For the first n lines, the i-th line contains two numbers: the i-th input number and the number less than it when inserted.
In the N + 1 line, the given n numbers are output from small to large, separated by spaces, and there is no space at the end of the line.
###Input example:
Here is a set of inputs. For example:
```in
ten
89 2 21 534 12 423 542 35 11 21
```
###Output example:
The corresponding output is given here. For example:
```out
89 0
2 0
21 1
534 3
12 1
423 4
542 6
35 3
11 1
21 3
2 11 12 21 21 35 89 423 534 542
```
answer：If there is no answer, please comment