#P5181. [COCI2009-2010#1] GENIJALAC

[COCI2009-2010#1] GENIJALAC

题目描述

译自 COCI 2009.10 T5「GENIJALAC

Mirko 发明了一台打乱机。机器接受一个 NN 列、无限行的纸带作为输入和输出。这 NN 列依次编号为 1N1\ldots N

开始时,只有纸带的第一行写了数,其下方的每一行都是空白的。
在纸带的第一行中,每列有一个整数,第 ii 列上写了整数 ii
另外,Mirko 给出了一个打乱排列,这是一个长度为 NN 的排列 s1,s_1, s2,s_2, ,\ldots, sNs_N

有一个行指针,开始时指向首行。
每次运行该机器时,机器会将当前行(行指针所指向的行)位于第 ii 列的数放到下一行的第 sis_i 列上,NN 个数都放好后,指针将下移一行。

Mirko 运行了该机器无限次。现在 Mirko 将纸带的前 CC 列和后 DD 列剪掉了,我们称之为新的纸带。

试问:在新纸带的第 ABA\sim B 行中,有多少行与新纸带的首行相同。

输入格式

第一行五个整数 N,A,B,C,DN, A, B, C, D
第二行 NN 个整数 s1,s_1, s2,s_2, ,\ldots, sNs_N

输出格式

一行,一个整数,表示在新纸带的第 ABA\sim B 行中,有多少行与新纸带的首行相同。

4 1 5 0 1
1 3 4 2
2
7 3 8 1 2
2 3 1 6 4 7 5
0
6 2 11 3 0
6 3 5 4 2 1
1

提示

样例说明 1

+-----+
|1 2 3|4 <--
|1 3 4|2
|1 4 2|3
|1 2 3|4 <--
|1 3 4|2
+-----+
 1 4 2 3
 1 2 3 4

样例说明 2

1 2 3 4 5 6 7
2 3 1 6 4 7 5
 +-------+
3|1 2 7 6|5 4
1|2 3 5 7|4 6
2|3 1 4 5|6 7
3|1 2 6 4|7 5
1|2 3 7 6|5 4
2|3 1 5 7|4 6
 +-------+
3 1 2 4 5 6 7
1 2 3 6 4 7 5

样例说明 3

1 2 3 4 5 6
     +-----+
6 3 5|4 2 1|
1 5 2|4 3 6|
6 2 3|4 5 1|
1 3 5|4 2 6|
6 5 2|4 3 1|
1 2 3|4 5 6| <--
6 3 5|4 2 1|
1 5 2|4 3 6|
6 2 3|4 5 1|
1 3 5|4 2 6|
     +-----+

数据范围与提示

对于 40%40\% 的数据,A,A, B,B, C,C, D,D, N2000N\le 2000
对于所有数据,1N5×105,1\le N\le 5\times 10^5, 1A,B1012,1\le A, B\le 10^{12}, 0C,0\le C, DN,D\le N, C+DNC+D\le N