Alice is playing a game with his friend Bob on a permutation P of length N. Two players take turns choosing numbers while Alice going first.

In each round, the player should pick an element in P that is larger than any element chosen by two players previously. Besides that, if one player picked  before, the element  he picks in this round should satisfy with . If there are mutiple chooses, the player will randomly pick an element that satisfies all the conditions with equal probability.

In the first round, each player could choose an element in any position, but Bob should choose an element bigger than the first element chosen by Alice. The game ends immediately when a player couldn't find an appropriate element to pick.

Alice and Bob wonder what is the expected number of rounds. Here the expected number we calculate is the sum of steps of two players.

The first line contains one integer , describing the length of P.

The second line contains  integers ,describing permutation P.

Output the answer in one line. If the expected number is , print .

3
1 2 3

831870296

3
3 1 2

665496237

8
1 5 2 6 3 7 4 8

904361851