The Third Problem (Codeforces 1699C)
Tags: Math, combinatorics

You are given a permutation $$$a_1,a_2,\ldots,a_n$$$ of integers from $$$0$$$ to $$$n - 1$$$. Your task is to find how many permutations $$$b_1,b_2,\ldots,b_n$$$ are similar to permutation $$$a$$$. Two permutations $$$a$$$ and $$$b$$$ of size $$$n$$$ are considered similar if for all intervals $$$[l,r]$$$ ($$$1 \le l \le r \le n$$$), the following condition is satisfied: $$$$$$\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]),$$$$$$ where the $$$\operatorname{MEX}$$$ of a collection of integers $$$c_1,c_2,\ldots,c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in collection $$$c$$$. For example, $$$\operatorname{MEX}([1,2,3,4,5])=0$$$, and $$$\operatorname{MEX}([0,1,2,4,5])=3$$$.Since the total number of such permutations can be very large, you will have to print its remainder modulo $$$10^9+7$$$.In this problem, a permutation of size $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$0$$$ to $$$n-1$$$ in arbitrary order. For example, $$$[1,0,2,4,3]$$$ is a permutation, while $$$[0,1,1]$$$ is not, since $$$1$$$ appears twice in the array. $$$[0,1,3]$$$ is also not a permutation, since $$$n=3$$$ and there is a $$$3$$$ in the array.

Input: Each test contains multiple test cases. The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The following lines contain the descriptions of the test cases.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the size of permutation $$$a$$$.The second line of each test case contains $$$n$$$ distinct integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt n$$$) — the elements of permutation $$$a$$$.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$.

Output: For each test case, print a single integer, the number of permutations similar to permutation $$$a$$$, taken modulo $$$10^9+7$$$.

Note: For the first test case, the only permutations similar to $$$a=[4,0,3,2,1]$$$ are $$$[4,0,3,2,1]$$$ and $$$[4,0,2,3,1]$$$.For the second and third test cases, the given permutations are only similar to themselves.For the fourth test case, there are $$$4$$$ permutations similar to $$$a=[1,2,4,0,5,3]$$$:   $$$[1,2,4,0,5,3]$$$;  $$$[1,2,5,0,4,3]$$$;  $$$[1,4,2,0,5,3]$$$;  $$$[1,5,2,0,4,3]$$$. 

Sample Inputs:
5
5
4 0 3 2 1
1
0
4
0 1 2 3
6
1 2 4 0 5 3
8
1 3 7 2 5 0 6 4

Sample Outputs:
2
1
1
4
72

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    m = 10 ** 9 + 7
    if n <= 2:
        return 1
    pos = [-1] * n
    for i in range(n):
        pos[arr[i]] = i
    (f, b) = (min(pos[0], pos[1]), max(pos[0], pos[1]))
    curr = b - f - 1
    ans = 1
    for i in range(2, n):
        if f < pos[i] < b:
            ans *= curr
            ans %= m
            curr -= 1
        elif pos[i] < f:
            curr += f - pos[i] - 1
            f = pos[i]
        else:
            curr += pos[i] - b - 1
            b = pos[i]
    return ans
for _ in range(int(input())):
    print(solve())

Solution (Python):
import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    if n == 1:
        print(1)
        continue
    idx = {l[i]: i for i in range(n)}
    ans = 1
    le = idx[0]
    ri = idx[1]
    if le > ri:
        (le, ri) = (ri, le)
    for i in range(2, n):
        if le < idx[i] < ri:
            ans *= ri - le + 1 - i
            ans %= mod
        else:
            le = min(le, idx[i])
            ri = max(ri, idx[i])
    print(ans)

Solution (Python):
for __ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    array = [0] * n
    for i in range(n):
        array[a[i]] = i
    if n == 1:
        print(1)
    else:
        l = min(array[0], array[1])
        r = max(array[0], array[1])
        ans = 1
        t = 10 ** 9 + 7
        for i in range(2, n):
            if l < array[i] < r:
                ans = ans * (r - l + 1 - i) % t
            else:
                l = min(array[i], l)
                r = max(array[i], r)
        print(ans % t)