圣诞节到了,圣诞老人要给孩子们送礼物。圣诞老人共准备了n件礼物,为了更好地完成礼物的派送,圣诞老人对这些礼物依次编号为1,2,3,……,n,并将其一次放入一个高高的箱子中,嗯嗯,箱子很高,并且每一层只能放一件礼物,最上面的礼物的编号为a1,下一个的编号为a2,以此类推,最下面的礼物的编号为an(类似栈的概念)。很显然,ai不等于aj(当i不等于j时),且1<=ai,aj<=n。
为了有序地给孩子们发放礼物,圣诞老人拟定了一份礼物清单为b1, b2,……bm,显然,bi不等于bj(当i不等于j时),且1<=bi,bj<=n。他将按b1, b2,……bm的顺序依次发放礼物。
要发送礼物,圣诞老人必须从礼物箱子中找到它。为了拿到编号为t的礼物,圣诞老人首先需要移除t上面所有的礼物,然后拿走编号为t的礼物,最后将所有移除的礼物再重新放回箱子中。我们都知道,圣诞老人的能力很强,他可以1秒钟从箱子中拿出一件礼物或者将一件礼物放回箱子中。所以,如果圣诞老人想要送的礼物上面有k件礼物,他需要2k+1秒才能送完。幸运的是,圣诞老人可以加快整个过程:当他把礼物重新放回箱子中时,他可以按照自己的意愿重新排列它们(只有那些在礼物t的上面的礼物可以重排,因为这些需要重新放回箱子里,t下面的礼物不会受到任何影响)。
如果圣诞老人知道他要送的礼物清单,并以最佳方式重新排列,那么发送所有礼物所需的最短时间是多少?