TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5913
  • 問題
  • P5913【崛起的欢乐赛】大圣归来
    制限 : 時間制限 : - MS   メモリ制限 : 262144 KB
    問題説明

    他曾经大闹天宫,被如来佛压在五行山下五百多年。他逃出山洞,但是法力尽失,性格狂躁抑郁,看淡功与名,只想回花果山过平凡日子。

    大圣走到花果山下,发现有另外$n-1$只猴子正排着队上花果山。大圣现在没有法力,只能老老实实排在队伍的最后,也就是排在第$n$个。

    花果山的猴子都很有素质,懂得礼让,它们的礼让规则很简单,体型大的猴子会主动让体型小的猴子排到自己前面。为了方便,设这$n$只猴子的体型大小分别是$a_1,a_2,\dots,a_n$,这$n$只猴子的体型大小互不相同,其中$a_n$表示大圣的体型大小。每一秒,除了排在最后的一只猴子,其他猴子都会观察自己正后方一只猴子的体型,如果正后方一只猴子的体型比自己小,就会在这一秒允许一只猴子插队到自己前面去,但插队的猴子不要求必须是自己后方的第一只猴子。如果某只猴子和他前面的一只猴子在这一秒都允许插队,则这只猴子会将插队到前面的机会让给插自己队的猴子。猴子们从观察到完成插队的整个过程只需要$1$秒,而下一秒,猴子们会进行下一轮的观察和插队。

    举个例子,假设现在有$4$只猴子在排队,体型分别是$2,4,3,1$。在第$1$秒,体型为$4$和$3$的两只猴子允许后面的一只猴子插队,这时体型为$3$的猴子会将体型为$4$的猴子提供的插队机会让给体型为$1$的猴子;但体型为$4$的猴子只允许一只猴子插队,所以体型为$3$的猴子仍然在体型为$4$的猴子的后面。所以第$1$秒结束时,排队的猴子体型依次是$2,1,4,3$。在第$2$秒,体型为$2$和$4$的两只猴子允许后面的一只猴子插队。所以第$2$秒结束时,排队的猴子体型依次是$1,2,3,4$。从第$3$秒开始,就不会再发生礼让和插队的事件。

    现在大圣想知道,自己的位置会在哪些时候发生什么样的变化。

    入力形式

    第一行一个正整数$n$,表示排队的猴子数量,其中大圣是第$n$个。

    第二行$n$个互不相同的正整数$a_1,a_2,\dots,a_n$,表示排队的每只猴子的体型。

    出力形式

    输出若干行,每行两个正整数$x,y$,表示第$x$秒结束时大圣的位置发生了变化,变成了队伍的第$y$只猴子。请按$x$由小到大的顺序输出,而在大圣位置不发生变化的时刻不要输出任何东西。

    サンプル入力 1

    4
    2 4 3 1

    サンプル出力 1

    1 2
    2 1

    サンプル入力 2

    8
    4 7 2 8 6 5 1 3

    サンプル出力 2

    2 5
    3 4
    4 3

    ヒント

    样例说明1

    大圣在第$1$秒结束时变成了队伍的第$2$只猴子,在第$2$秒结束时变成了队伍的第$1$只猴子。

    样例说明2

    第$1$秒结束时,排队的猴子体型依次是$4,2,7,1,8,6,5,3$,这一秒大圣位置没有变化;
    第$2$秒结束时,排队的猴子体型依次是$2,4,1,7,3,8,6,5$,这一秒大圣位置从第$8$个变成了第$5$个;
    第$3$秒结束时,排队的猴子体型依次是$2,1,4,3,7,5,8,6$,这一秒大圣位置从第$5$个变成了第$4$个;
    第$4$秒结束时,排队的猴子体型依次是$1,2,3,4,5,7,6,8$,这一秒大圣位置从第$4$个变成了第$3$个;
    第$5$秒结束时,排队的猴子体型依次是$1,2,3,4,5,6,7,8$,这一秒大圣位置没有变化。
    此后不会再发生礼让和插队事件。

    数据规模与约定

    对于5%的数据,\(n=3\)
    对于5%的数据,\(n=4\)
    对于20%的数据,\(n\le 20\)
    对于50%的数据,\(n\le200\)
    对于100%的数据,$3\le n\le2000,\ 1\le a_i\le n$。


    ソース  感谢nodgd命题