#P5274. lian

    ID: 4312 传统题 8000ms 512MiB 尝试: 11 已通过: 4 难度: 9 上传者: 标签>CF2700省选/NOI-可持久化线段树前缀版本作差随机哈希双哈希快速选择同向双指针二叉堆

lian

Description

首先我们定义两个多重集A和B的大小关系,找到最小的整数x使得在两个多重集中出现次数不同,然后整数x出现次 数大的多重集更小。如果这样的x不存在,那么相等。 比如{1,2,3}<{1,3,3,5},{1,1,4,4}<{1,1,4}。 给你一个长为n的序列,序列中每个数字在1到n之间。 对于任意一个区间[l,r],这里面的数字a_l,a_{l+1},…,a_r会形成一个多重集,一共形成n*(n+1)/2个多重集。 现在请输出这些多重集中第p小的到第q小的多重集对应的区间是什么 如果两个多重集一样大,那么我们认为对应的区间的左端点较小的更小。

Format

Input

第一行三个正整数n,p,q

接下来一行n个1到n之间的整数,表示这个序列,序列下标从1开始标号。

n<=100000,1<=p<=q<=n*(n+1)/2且q<=p+100000

Output

输出q-p+1行,每行两个正整数表示多重集对应的区间。

Samples

6 10 13
1 2 1 3 5 1
2 3
3 5
4 6
3 4