406405: GYM102396 J Superpermutations

Once, during his informatics class, Dima had solved all the problems about permutations. Then he came up with a problem about a superpermutation.

A superpermutation of order $$$n$$$ is a sequence of integers from $$$1$$$ to $$$n$$$, such that every permutation of numbers from $$$1$$$ to $$$n$$$ occurs as a continuous subsegment in this sequence.

Dima quickly came up with an algorithm for generating superpermutations:

• $$$s_1 = [1]$$$.
• Initially, set $$$s_{n+1}$$$ equal to $$$s_n$$$.
• Consider all subsegments of $$$s_n$$$ of length $$$n$$$ from left to right, in order of increasing of their beginning.
• If a current subsegment $$$s_n[l, l+1, \ldots, l+n-1]$$$ is a permutation of numbers from $$$1$$$ to $$$n$$$ (that means that every number from $$$1$$$ to $$$n$$$ occurs exactly once), then insert numbers $$$n + 1, s_n[l], s_n[l + 1], \ldots, s_n[l+n-1]$$$ into $$$s_{n+1}$$$ right after the last element $$$s_n[l+n-1]$$$ of the corresponding subsegment.

Let's take a look at how to construct superpermutations of order $$$1$$$, $$$2$$$, $$$3$$$ and $$$4$$$:

By definition, $$$s_1 = [ 1 ]$$$.

Set $$$s_2 = [ 1 ]$$$. Consider the only subsegment of length $$$1$$$ in $$$s_1$$$: $$$[1]$$$ is a permutation, so we insert $$$[2, 1]$$$ into $$$s_2$$$ after it. The result is $$$s_2 = [1, \mathbf{2, 1}]$$$.

Set $$$s_3 = [ 1, 2, 1 ]$$$. Consider all subsegments of length $$$2$$$ in $$$s_2$$$. $$$[1, 2]$$$ is a permutation, after inserting $$$[3, 1, 2]$$$, we get $$$s_3 = [1, 2, \mathbf{3, 1, 2}, 1]$$$. $$$[2, 1]$$$ is also a permutation, so we insert $$$[3, 2, 1]$$$ into $$$s_3$$$, we get $$$s_3 = [1, 2, 3, 1, 2, 1, \mathbf{3, 2, 1}]$$$.

Initially, set $$$s_4 = [ 1, 2, 3, 1, 2, 1, 3, 2, 1]$$$. Consider all subsegments of length $$$3$$$ in $$$s_3$$$:

• $$$[1, 2, 3]$$$ is a permutation, so we insert $$$[4, 1, 2, 3]$$$ after it. Now $$$s_4 = [ 1, 2, 3, \mathbf{4, 1, 2, 3}, 1, 2, 1, 3, 2, 1]$$$.
• $$$[2, 3, 1]$$$ is a permutation, so we insert $$$[4, 2, 3, 1]$$$ after it. Now $$$s_4 = [ 1, 2, 3, 4, 1, 2, 3, 1, \mathbf{4, 2, 3, 1}, 2, 1, 3, 2, 1]$$$.
• $$$[3, 1, 2]$$$ is a permutation, so we insert $$$[4, 3, 1, 2]$$$ after it. Now $$$s_4 = [ 1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, \mathbf{4, 3, 1, 2}, 1, 3, 2, 1]$$$.
• $$$[1, 2, 1]$$$ is not a permutation, so nothing happens here, we continue with the next subsegment.
• $$$[2, 1, 3]$$$ is a permutation, so we insert $$$[4, 2, 1, 3]$$$ after it. Now $$$s_4 = [ 1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 3, 1, 2, 4, 3, 1, 2, 1, 3, \mathbf{4, 2, 1, 3}, 2, 1]$$$.
• We do the same with two remaining permutations of length 3: $$$[1, 3, 2]$$$ and $$$[3, 2, 1]$$$.

Dima noticed that he came up with a pretty efficient way of constructing a superpermutation, because every permutation occurs exactly once. To make sure he did not make a mistake, Dima wants to find a position where a given permutation $$$a_1, \dots, a_n$$$ occurs in his superpermutation $$$s_n$$$. Positions are numbered starting with 1.

Since the length of $$$s_n$$$ is huge, you need to find the index of the first element of $$$s_n$$$ from which the occurrence of the given permutation starts, modulo $$$10^9 + 7$$$.

The first line contains a single integer $$$n$$$ — the length of the permutation ($$$1 \le n \le 300\,000$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — the given permutation ($$$1 \le a_i \le n$$$, all $$$a_i$$$ are different).

Output a single integer — the position of the occurrence of the permutation $$$a_1, a_2, \ldots, a_n$$$ in the superpermutation of order $$$n$$$, modulo $$$10^9+7$$$.

3
2 3 1

2

4
2 3 1 4

6

4
4 3 1 2

14