A7103 | 「TAOI-1」拼凑的断音

## 数据范围

**本题采用捆绑测试**。

- Subtask 1（20 points）：$n \leq 15$。
- Subtask 2（15 points）：保证 $\forall i \in [1, n), a_i \leq a_{i+1}$，$a_n \geq a_{n-1}+s$。
- Subtask 3（15 points）：保证 $\forall i,j\in[1,n], a_i = a_j$。
- Subtask 4（50 points）：无特殊限制。

对于所有测试数据，$1 \leq n \leq 10^5$，$1 \leq p \lt q \leq 10^7$，$1 \leq a_i,s \leq 10^7$。

## 样例解释

注意到两个样例的输入相同，区别仅在于输出格式不同。

以下列举了所有可能的魔法施加情况和其对应的最大值以及出现概率：

| 魔法情况 | 动听度最大值 | 出现概率 | 对期望的贡献 |
| :------: | :----------: | :------: | :----------: |
|${\color{black}1},{\color{black}2},{\color{black}3}$|$3$|$\dfrac{8}{27}$|$\dfrac{8}{9}$|
|${\color{red}3},{\color{black}2},{\color{black}3}$|$3$|$\dfrac{4}{27}$|$\dfrac{4}{9}$|
|${\color{black}1},{\color{red}4},{\color{black}3}$|$4$|$\dfrac{4}{27}$|$\dfrac{16}{27}$|
|${\color{black}1},{\color{black}2},{\color{red}5}$|$5$|$\dfrac{4}{27}$|$\dfrac{20}{27}$|
|${\color{red}3},{\color{red}4},{\color{black}3}$|$4$|$\dfrac{2}{27}$|$\dfrac{8}{27}$|
|${\color{red}3},{\color{black}2},{\color{red}5}$|$5$|$\dfrac{2}{27}$|$\dfrac{10}{27}$|
|${\color{black}1},{\color{red}4},{\color{red}5}$|$5$|$\dfrac{2}{27}$|$\dfrac{10}{27}$|
|${\color{red}3},{\color{red}4},{\color{red}5}$|$5$|$\dfrac{1}{27}$|$\dfrac{5}{27}$|

可得，最终的答案为 $\dfrac{35}{9}$。

它的值约为 $3.888889$。