Description
Story
RedCapeFlyingCat wants a class photo of all the penguins in Data Structures, lined up from shortest to tallest. The penguins refuse to walk far, so they only ever swap with the penguin next to them. RedCapeFlyingCat wants to know how much work this will take.
Problem Statement
You are given an array of integers . Find:
- For each , the number of indices such that and .
- The number of swaps performed when the following bubble sort runs on :
for p = 1 .. N-1:
for i = 1 .. N-p:
if A[i] > A[i+1]:
swap(A[i], A[i+1]) // this counts as one swap
What Is Bubble Sort?
Bubble sort puts an array in non-decreasing order by comparing neighbouring elements.
- It makes passes. Each pass walks through the array from left to right.
- At each step it compares two neighbouring elements. If the left one is larger, it swaps them. If they are equal, it does nothing.
- Each pass moves the largest remaining element to its final place at the end, so the next pass stops one position earlier.
The sample explanation lists every swap.
Input
- Line 1: .
- Line 2: .
Constraints
- Values in may repeat.
Output
- Line 1: integers separated by spaces. The -th integer is the number of indices such that and .
- Line 2: One integer, the number of swaps.
There must be no trailing space at the end of Line 1.
Sample Input Download
Sample Output Download
Explanation
Line 1: For example, has two larger elements before it ( and ). has none, because the before it is equal, not larger.
Line 2: Bubble sort performs swaps. Only the steps that swap are listed. The two s are never swapped.
| Pass | Swap | Array after the swap | Swaps so far |
|---|---|---|---|
| Start | |||
| and | |||
| and | |||
| and | |||
| and | |||
| and | |||
| and |