HMR的LIS Ⅲ

题目背景

[HMR的LIS Ⅰ](https://www.luogu.org/problemnew/show/T51390) [HMR的LIS Ⅱ](https://www.luogu.org/problemnew/show/T51391) 在你帮助HMR切掉AKIOI的神仙LSK的两道题后,LSK很不满,决定好好刁难一下你(而不是HMR)

题目描述

LSK又给出了一个长度为n的序列,要求你求出它的IBvl序列 IBvl序列满足以下要求: 1.一个IBvl序列满足$ \forall ~ i \in (1,len] , L < a_i - a_{i-1} < R $,其中$len$为IBvl序列的长度 2.IBvl序列中的元素相对顺序应满足在原序列中的相对顺序 3.在所有满足条件的序列中长度最长 我们视位置不同的元素为不同元素,有任一组成元素不同的IBvl序列为不同IBvl序列 现在要求你输出原序列的IBvl序列的长度,并输出字典序第k小(以元素在原序列中的位置为关键字排序)的序列的每个元素在原序列中的位置

输入输出格式

输入格式


第一行输入4个整数,n,k,L,R 第二行输入n个整数,表示神仙LSK给出的序列

输出格式


第一行输出IBvl序列的长度 第二行输出IBvl序列的每个元素的位置

输入输出样例

输入样例 #1

5 3 2 4
6 8 0 2 7

输出样例 #1

1
3

说明

#### 样例解释: 对于给出的数据,一共有$5$种IBvl序列,分别是:$\{6\},\{8\},\{0\},\{2\},\{7\}$。 他们在原序列中位置的编号序列分别是$\{1\},\{2\},\{3\},\{4\},\{5\}$ IBvl序列的长度为1。 要求输出字典序第$3$小的编号序列,于是输出$3$。 #### 数据范围与约定: 对于20%的数据,$ n \le 18$ 对于50%的数据,$ n \le 1000 , | l | , | r | \leq 10^9 , r-l>1 , 0 \le a[i] \le 10^9 $ 对于另外10%的数据,$ l=0 , r=10^9+1 , k=1 $ 对于另外20%的数据,$ l=0 , r=10^9+1 , k \le 3 $ 对于100%的数据,$ n \le 5*10^5 , | l | , | r | \le 10^9 , r-l>1 , k \le 10^{13} , 0 \le a[i] \le 10^9 $ 对于所有数据,保证合法且有解。 对于前50%的数据,时限为1s,后50%的数据,时限为2s(~~凉~~良心不卡常)