All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

Jiraiya and Rasengan Attacks
Tag(s):

BIT, Expectation, Medium

Problem
Editorial
Analytics

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

enter image description here

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$$

SAMPLE INPUT
3
1 2 3
SAMPLE OUTPUT
833333340
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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

June Circuits

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications