SOLVE

LATER

Jiraiya and Rasengan Attacks

/

Naruto has started training from Jiraiya to develop the most powerful *Rasengan* attack. Jiraiya as always uses weird training exercises.

Jiraiya has brought a permutation *P* of \(1,2..\space N\) integers. He tells Naruto to sort the permutation using *minimum* number of *Rasengan* attacks. In one *Rasengan* attack Naruto can choose any pair of consecutive elements of the permutation and swap it.

To make the task a little difficult, he chooses a subsegment of the permutation *uniformly* at random \(P_L, P_{L+1},.., P_R\) (L ≤ R) and reverses it to make \(P_1, P_2,..,P_{L-1}, P_R,.., P_{L+1}, P_L, P_{R+1},..,P_N\space \). Now he asks Naruto to tell the expected number of *Rasengan* attacks he need to sort the permutation.

**INPUT**

The first line contains the integer *N*.

The next line contains *N* integers denoting the permutation *P*.

**OUTPUT**

Print \((A * B^{-1}) \space mod\space 10^9+7\) where \(\frac{A}{B}\) is the **Expected value** of number of *Rasengan* attacks he need to sort *P* (expressed as an irreducible fraction)

**CONSTRAINTS**

\(2 ≤ N ≤ 10^5\)

Explanation

The 6 ways of reversing a subarray is

- 1,1 -> 1,2,3.
*Rasengan*attacks = 0 - 2,2 -> 1,2,3.
*Rasengan*attacks = 0 - 3,3 -> 1,2,3.
*Rasengan*attacks = 0 - 1,2 -> 2,1,3.
*Rasengan*attacks = 1 - 2,3 -> 1,3,2.
*Rasengan*attacks = 1 - 1,3 -> 3,2,1.
*Rasengan*attacks = 3

Probability of getting *Rasengan* attacks = 0 is \(\frac{3}{6}\)

Probability of getting *Rasengan* attacks = 1 is \(\frac{2}{6}\)

Probability of getting *Rasengan* attacks = 3 is \(\frac{1}{6}\)

Expected value of *Rasengan* attacks = \(\frac{3}{6} * 0 + \frac{2}{6} * 1 + \frac{1}{6} * 3 = \frac{5}{6} \equiv 833333340 \space mod \space 10^9+7\)

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...