CF1461C.Random Events

Ron is a happy owner of a permutation $a$ of length $n$.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Ron's permutation is subjected to $m$ experiments of the following type: ($r_i$, $p_i$). This means that elements in range $[1, r_i]$ (in other words, the prefix of length $r_i$) have to be sorted in ascending order with the probability of $p_i$. All experiments are performed in the same order in which they are specified in the input data.

As an example, let's take a look at a permutation $[4, 2, 1, 5, 3]$ and an experiment ($3, 0.6$). After such an experiment with the probability of $60\%$ the permutation will assume the form $[1, 2, 4, 5, 3]$ and with a $40\%$ probability it will remain unchanged.

You have to determine the probability of the permutation becoming completely sorted in ascending order after $m$ experiments.

罗恩拥有一组长度为 $n$ 的排列 $a$，他为此感到非常开心。

长度为 $n$ 的排列是指由 $1$ 到 $n$ 中互不相同的 $n$ 个整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中却出现了 $4$）。

罗恩的排列将依次经历 $m$ 次实验，每次实验形如 $(r_i, p_i)$：表示以概率 $p_i$ 将排列中前 $r_i$ 个元素（即长度为 $r_i$ 的前缀）按升序排序。所有实验严格按照输入中给出的顺序执行。

举个例子，考虑排列 $[4, 2, 1, 5, 3]$ 和一次实验 $(3, 0.6)$：此次实验将以 $60\%$ 的概率使排列变为 $[1, 2, 4, 5, 3]$，并以 $40\%$ 的概率保持不变。

你需要计算：经过全部 $m$ 次实验后，该排列完全按升序排好（即变为 $[1,2,\dots,n]$）的概率。

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$).

The first line of each test case contains two integers $n$ and $m$ $(1 \le n, m \le 10^5)$ — the length of the permutation and the number of experiments, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le n)$ — contents of the permutation.

The following $m$ lines of each test case each contain an integer $r_i$ and a real number $p_i$ $(1 \le r_i \le n, 0 \le p_i \le 1)$ — the length of the prefix and the probability of it being sorted. All probabilities are given with at most $6$ decimal places.

It is guaranteed that the sum of $n$ and the sum of $m$ does not exceed $10^5$ ($\sum n, \sum m \le 10^5$).

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^5$），分别表示排列的长度和实验次数。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示该排列的内容。

每个测试用例接下来的 $m$ 行，每行包含一个整数 $r_i$ 和一个实数 $p_i$（$1 \le r_i \le n,\ 0 \le p_i \le 1$），分别表示前缀长度以及该前缀已排序的概率。所有概率均以最多 $6$ 位小数给出。

保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $10^5$（即 $\sum n, \sum m \le 10^5$）。

For each test case, print a single number — the probability that after all experiments the permutation becomes sorted in ascending order. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.

对于每个测试用例，输出一个数字——即在所有实验完成后，排列变为升序排列的概率。若你的答案的绝对误差或相对误差不超过 $10^{-6}$，则视为正确。

形式化地，设你的答案为 $a$，评测机的答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，你的答案被接受。

Explanation of the first test case: It can be demonstrated that whether the final permutation is sorted or not depends solely on sorting being performed in the $(4, 0.6)$ experiment.

第一个测试用例的说明：可以证明，最终排列是否有序仅取决于在 $(4, 0.6)$ 实验中是否执行了排序操作。