题目描述

有一个长为 $n$ 的数列，初始时为 $a_{1..n}$。

给你 $q$ 个操作，第 $i$ 个操作将 $[l_i,r_i]$ 内的数全部加一，有 $p_i$ 的概率被执行。保证区间不会交错，即：$\forall i,j\in[1,q],l_i\le r_i<l_j\le r_j$ 或 $l_i\le l_j\le r_j\le r_i$ 或 $l_j\le r_j<l_i\le r_i$ 或 $l_j\le l_i\le r_i\le r_j$ 。

求操作完成后数列的最大值的期望。

输入格式

第一行 $n,\,q\,(1\le n\le10^5,\,1\le q\le 5000)$。

第二行 $a_1,\,a_2,\,\cdots,\,a_n\,(0\le a_i\le10^9)$。

接下来 $q$ 行，每行 $l_i,\,r_i,\,p_i\,(1\le l_i\le r_i\le n,\,0\le p_i\le1)$。

输出格式

一个实数，表示答案，保留 $9$ 位小数。

5 2
1 7 2 4 3
1 3 0.500
2 2 0.500

8.000000000

5 2
281 280 279 278 282
1 4 1.000
1 4 0.000

282.000000000

3 5
1 2 3
1 3 0.500
2 2 0.250
1 2 0.800
1 1 0.120
2 2 0.900

4.465000000