Mohanad likes AtCoder.jp, which is a superior Japanese programming contest site.
One of the factors that make AtCoder.jp a great website is its short problem statements. Therefore, in true AtCoder.jp fashion, this problem statement is as short as possible.
Given a permutation $$$p$$$ of length $$$n$$$, let $$$P$$$ be an array of permutations that contains all permutations lexicographically greater than or equal to $$$p$$$, sorted by their order. Let $$$A$$$ be the concatenation of $$$P$$$.
How many swaps will bubble sort algorithm make to sort $$$A$$$?
The answer may be large, so output it modulo $$$10^9+7$$$.
(Check out the notes for bubble sort code).
The first line contains $$$n$$$ ($$$2 \le n \le 2000$$$).
The second line contains a permutations $$$p$$$.
The number of swaps the above code will make to sort $$$A$$$ modulo $$$10^9+7$$$.
3 3 1 2
8
6 3 4 2 1 6 5
1355278
In the first test case:
$$$P = [[3,1,2],[3,2,1]]$$$
$$$A = [3,1,2,3,2,1]$$$
Bubble Sort C++ code:
