【题目】

对于一个 $1$ 到 $n$ 的排列 $P$ （即 $1$ 到 $n$ 中每一个数在 $P$ 中出现了恰好一次）。

令 $q[i]$ 为第 $i$ 个位置之后第一个比 $P$ 值更大的位置，如果不存在这样的位置，则 $q[i]=n+1$ 。

举例来说，如果 $n=5$ 且 $P$ 为 $15423$ ，则 $q$ 为 $26656$ 。

下列程序读入了排列 $P$ ，使用双向链表求解了答案。试补全程序。

【解析】

先说说这道题怎么拿链表解决。

先找到最小的元素，是第1位的1，它右边不论是几都肯定比它大，所以这一位的答案就是右侧的第2位。
 此时把它从链表中删除，让前一位直接指向后一位。

再在链表中找到最小的元素，是第4位的2，它右边不论是几都比它大，所以这一位的答案是第5位。
 再从链表中把2删除，让前一位指向后一位。

继续这个过程，找到最小的元素是第5位的3，它右侧的元素肯定比它大，因此这一位的答案是第6位。
 然后从链表中把3删除，让前一位指向后一位。

继续，最小的元素是第3位的4，它右侧的元素（第6位）比它大，这一位答案是6。
         从链表中删除4。

最后只剩第2位的5，右侧（第6位）比它大，这一位答案是6。把它删除后，整个操作结束。

最终的答案就是过程中记录下的数据，第1位是2，第4位是5，第5位是6，第3位是6，第2位是6，
即答案数组2 6 6 5 6。

程序用的是双向链表， $L$ 和 $R$ 相当于分别存储了每个元素的上一位和下一位。
这样有什么好处呢？副产品会更多。
最终不止知道每个元素后面比它大的第一个元素在哪，还能知道前面比它大的第一个元素在哪。
第2个for循环，显然它是先把ii对应到a[i]，再对应到L和R数组，为什么呢？为了去掉每轮都要先寻找最小值的过程。先存一下第1小、第2小、第3小……的值依次出现在哪儿，每轮就能直那一位。

第1题：

$a[x]=i$ 因为正好是1~n的排列
$x$ 就表示第 $x$ 小的数
$a[x]=i$表示第 $x$ 小的数出现的位置
$p$ 数组：$15423$
$a$ 数组：$14532$

即最小的数出现在第1位，第2小在第4位……

第2题：

$i+1$
L记录前面第一个更大值的位置
R记录后面第一个更大值的位置
根据最值更新链表的过程，定位到当前的最小值后，就要从双向链表中将它删除。
$i$表示的是当前要找第$i$小的数，它的实际位置是 $a[i]$ ，所以 $i$ 与链表操作无直接关系，都是与 $a[i]$ 有关。
要让前一位和后一位直接互相指向，用自己的前一位更新后一位的前一位，用自己的后一位更新前一位的后一位。

第3题：

$R[a[i]]$

第4题：

$a[i]$
我们假定位置 $i$ 后边的最大数字的位置为 $i+1$，然后从最小的 $1$ 开始更新，让 $1$ 所在位置的前一位直接指向 $1$ 的后一位（ $1$ 不可能是 $1$ 所在位置的前一位的后边的第一个最大的，相当于删除了 $1$）。从小到大循环删除所有的不合法假定，剩下的就是答案。

第5题：

$R[i]$
$R$记录后面第一个更大值的位置