P12306 [ICPC 2022 WF] 移动集装箱

每天都有载有数千个集装箱宏伟货轮在海上航行。使用海运将货物运送到地球另一端的花费极低，这种高效的运输方式使现代贸易成为可能。 当货轮到达港口时，它所携带的标准尺寸集装箱就从船上卸下并堆叠在陆地上，然后再转运到火车或卡车上运送至最终目的地。事实证明，集装箱移动是一项费用高昂的工作，因此港口操作人员会尽量减少货物交付过程中的移动次数。 本题中，我们考虑这样一个集装箱卸载场景。我们需要卸载 $n$ 个集装箱，将它们放置在两个从底部向上建立的堆栈中。每个集装箱都随机放置，它们会等概率地被放在第一或第二个堆栈中（独立于其他集装箱）。所有集装箱都被卸载后，它们将按照给定的顺序装载到卡车上。当一辆卡车需要装一个特定的集装箱时，有两种情况。如果该集装箱在堆栈的顶部，那么它可以直接移动到卡车上而无需移动其他集装箱。否则，必须将集装箱从一个堆栈移动到另一个堆栈，直至所需集装箱位于堆栈的顶部，然后才能移动到卡车上。 例如，考虑三个集装箱按照 $1,2,3$ 的顺序到达的情况。假设 $1$ 和 $3$ 在第一个堆栈，$2$ 在第二个堆栈。如果集装箱按照 $1,2,3$ 的顺序装载到卡车上，那么需要进行 $5$ 次集装箱移动： | 堆栈 $1$ | 堆栈 $2$ | 注释 | | :------------: | :-------------: | :--------------------------------: | | `1 3` | `2` | 初始状态（自底向上） | | `1` | `2 3` | 将集装箱 $3$ 从堆栈 $1$ 移动到 $2$ | | | `2 3` | 将集装箱 $1$ 移动到卡车上 | | `3` | `2` | 将集装箱 $3$ 从堆栈 $2$ 移动到 $1$ | | `3` | | 将集装箱 $2$ 移动到卡车上 | | | | 将集装箱 $3$ 移动到卡车上 | 我们想知道把所有集装箱交付给客户所需的移动次数。假设集装箱的放置是随机的，请计算给定的卡车装载顺序所需的移动次数的期望。

第一行一个整数 $n$（$1\le n\le 10^6$），表示集装箱的数量。集装箱的编号为 $1, 2, \ldots , n$，并按此顺序从船上卸下。第二行包含 $n$ 个整数 $a_1, \ldots , a_n$。这些整数是 $\{1, 2, \ldots , n\}$ 的一个排列，表示集装箱装上卡车的顺序。

输出将集装箱装上卡车所需的移动次数的期望——这不包括将集装箱从船上卸下的移动次数，但包括在堆栈之间移动和从堆栈到卡车的移动。输出与答案之间的绝对误差应不超过 $10^{-3}$。