E
考虑枚举右端点 \(R\)，计算对于每个 \(R\) 有多少个左端点 \(L\) 满足条件。
左端点需要满足的条件如下：
- \([L, R]\) 中需要有 \(x\) 和 \(y\) 至少各一个。
- \([L, R]\) 中不能出现比 \(x\) 大或比 \(y\) 小的元素。
转化条件：
- 设 \(px\) 表示 \([1, R]\) 中最右边 \(x\) 的位置，\(py\) 表示 \([1, R]\) 中最右边 \(y\) 的位置，\(L \leqslant \min(px, py)\)。
- 设 \(gex\) 表示 \([1, R]\) 中最右边大于 \(x\) 的位置，\(ley\) 表示 \([1, R]\) 中最右边小于 \(y\) 的位置，\(L \gt \max(gex, ley)\)。
于是只需要在枚举 \(R\) 的同时维护 \(px, py, gex, ley\) 并将 \(\min(px, py) - \max(gex, ley)\) 计入答案即可。
时间复杂度 \(\Theta(n)\)。
F
考虑到每个数都需要存在，并且它在恰好两个位置中出现过（这两个位置可能相同），于是将这两个位置在一张图中连无向边。
观察到每个点度数都恰好为 \(2\)，于是连边后构成若干个环。
易知，整体方案数为每个环方案数的乘积，每个环的方案数为点覆盖方案数。
考虑求解大小为 \(m\) 的环的点覆盖方案数。考虑强行将环从 \(n \sim 1\) 处拆成链，设 \(f_{i, 0/1}\) 表示仅考虑 \(1 \sim i\) 的链，中间每条边都至少有一个端点被选，第 \(i\) 个点被选或不选的方案数。转移是简单的。但是我们发现最后计算答案时需要知道第一个点到底选没选，于是需要钦点第一个点选或不选分别转移。
将转移方程写出来后，我们观察到它其实是两个斐波那契状物之和，于是用数列 \(f_{1} = 1, f_{2} = 3, f_{i} = f_{i - 1} + f_{i - 2}\) 来拟合是可行的（当然也可以直接算，复杂度不变，代码也没长多少）。
综上即可算出原问题答案，时间复杂度 \(\Theta(n)\)。
