D. Jabberwocky

时间限制:1s

空间限制:64MB

本题分值:200

题目背景

'Twas brillig，and the slithy toves Did gyre and gimble in the wabe

All mimsy were the borogoves， And the mome raths outgrabe. '

为了打败恶龙 Jabberwocky， 国王决定举行一场比武大赛，选出两位最强大的勇士讨伐恶龙。

题目描述

共有编号为 \(1\) ~ \(n\) 的 \(n\) 位勇士参加比赛，每位勇士有力量 \(a_i\) 。

比赛由若干轮组成。每一轮比赛，编号最小的勇士与编号次小的勇士进行比试；编号第三小的勇士与编号第四小的勇士进行比试，以此类推。 特别地 ，若当前轮的人数是奇数，编号最大的选手将 轮空 ，直接进入下一轮。

一次比试中，力量值较大者获胜，可以进入下一轮，另一位选手淘汰。 特别地 ，若两者力量相同， 编号较小 的选手进入下一轮，编号较大的选手淘汰。

当最终仅剩 \(2\) 人时，比赛结束。请问，到达最后一轮的两位勇士的编号分别是多少？（请先输出 编号较小 的那一个。）

输入格式

第一行包含一个正整数\(n\)，表示勇士的人数。

第二行包含\(n\)个正整数\(a_i\)，表示第\(i\)位勇士的力量

输出格式

包含两个整数\(num_1<num_2\)，用空格隔开。从小到大表示最终两位勇士的编号。

样例输入1

5
1 4 2 4 3

样例输出1

2 5

样例1解释

\([1,4,2,4,3]\)

第一轮： 1号与2号；3号与4号比试，其中2号、4号进入下一轮，最后一位选手轮空

\([4,4,3]\)

第二轮：2号与4号比试，他们力量相同，但2号选手编号较小，所以2号进入下一轮。

最后一位选手轮空。

\([4,3]\)

此时只剩下两位勇士，比赛结束，编号分别是2,5。

样例输入2

7
1 20 21 4 7 2 6

样例输出2

3 5

样例2解释

\([1,20,21,4,7,2,6]\) -> \([20,21,7,6]\) -> \([21,7]\)

对应的是3号和5号

注意，需要按编号大小顺序输出

样例输入3

70
742435822 31849862 15676040 474199346 349572783 547484267 748131721 126060240 68556316 613241729 979717350 352379901 482076259 947368529 772086623 9172518 691171089 566424778 899215273 268669372 161004141 167202567 264933293 793233798 94940988 885814173 522164607 47863138 276876388 657368645 738936347 198232006 731166923 614025305 57355878 346041199 321694095 141810097 842935756 64610411 73430873 497069133 322510079 971151303 264232321 749415629 436886948 512345943 736323178 228373563 721196152 746022996 398962586 713215546 552942646 145310753 341897610 399870476 146758669 54701705 834512175 223405246 763533144 132255314 169487753 17348749 315627029 458868313 585960214 20795203 

样例输出3

11 69

数据范围及限制

对于所有测试点，\(1\le a_i\le 10^9\)

测试点编号	约定	测试点分值
1~10	\(2\le n\le 100\)	每个测试点10分
11~20	\(2\le n\le 10^5\)	每个测试点10分