瓶子投掷题
题号：NC308006
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}有 n 个柱子，第 i 根柱子的高度为 p_i（保证 p 为一个从 1 到 n 的排列）。
\hspace{15pt}每根柱子上有一个人，现在他们要开始扔瓶子了。第 i 个人能将瓶子扔到第 j \ (1 \leq j \leq n;\, i \neq j) 个人处，当且仅当满足以下三个条件：
\hspace{23pt}\bullet\,p_j>p_i；
\hspace{23pt}\bullet\,\forall i\le k<j,p_k<p_j；
\hspace{23pt}\bullet\,\forall j<k\le i,p_k<p_j；
\hspace{15pt}一个人拿到瓶子后会等概率随机地选择一个他能扔到的人，将瓶子扔过去，这会花费 1 单位的时间。如果这个人无法将瓶子扔到任何人手里，瓶子就会停在他手里。
\hspace{15pt}请你对于 i\in[1,n]，求出瓶子刚开始在第 i 个人手里时，瓶子停下的期望时间。可以证明答案可以表示为一个不可约分数 \tfrac{p}{q}，为了避免精度问题，请直接输出整数 \left(p \times q^{-1} \bmod M\right) 作为答案，其中 M = (10^9+7)，q^{-1} 是满足 q\times q^{-1} \equiv 1 \pmod{M} 的整数。

输入描述:

\hspace{15pt}第一行输入一个整数 n \left(1 \leq n \leq 10^6\right)，表示柱子数量。
\hspace{15pt}第二行输入 n 个两两不同的整数 p_1,p_2,p_3,\dots,p_n \left(1 \leq p_i \leq n\right)，表示第 i 根柱子的高度。

输出描述:

\hspace{15pt}在一行上输出 n 个整数，第 i 个整数表示若刚开始瓶子在第 i 个人手里，瓶子停下的期望时间对 10^9+7 取模的结果。
示例1

输入

复制 
4
1 3 2 4

输出

复制 
500000005 1 500000005 0

说明

\hspace{15pt}在这个样例中：
\hspace{23pt}\bullet\,若瓶子刚开始在第 4 个人手里，那么他无法将瓶子扔给任何人，所以瓶子在时刻 0 停下；
\hspace{23pt}\bullet\,若瓶子刚开始在第 2 个人手里，那么他只能将瓶子扔给第 4 个人，所以瓶子在时刻 1+0=1 停下；
\hspace{23pt}\bullet\,若瓶子刚开始在第 3 个人手里，那么他可以将瓶子扔给第 2 个人或者第 4 个人，由于扔给两个人的概率相等，均为 \tfrac{1}{2}，所以瓶子期望在时刻 1+\tfrac{1}{2}\times(1+0)=\tfrac{3}{2} 停下；
\hspace{23pt}\bullet\,若瓶子刚开始在第 1 个人手里，那么他可以将瓶子扔给第 2 个人或者第 4 个人，由于扔给两个人的概率相等，均为 \tfrac{1}{2}，所以瓶子期望在时刻 1+\tfrac{1}{2}\times(1+0)=\tfrac{3}{2} 停下。

\hspace{15pt}我们能够找到，500\,000\,005 \times 2 = 1\,000\,000\,010，对 10^9+7 取模后恰好等于分子 3，所以 500\,000\,005 是需要输出的答案。
示例2

输入

复制 
10
9 8 10 3 2 5 4 6 7 1

输出

复制 
1 500000005 0 83333336 483333339 833333341 83333336 500000005 1 500000005

备注: