题目描述

译自 COCI 2009.10 T5. GENIJALAC

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

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

有一个行指针，开始时指向首行。 每次运行该机器时，机器会将当前行（行指针所指向的行）位于第 $i$ 列的数放到下一行的第 $s_i$ 列上，$N$ 个数都放好后，指针将下移一行。

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

试问：在新纸带的第 $A\sim B$ 行中，有多少行与新纸带的首行相同。

输入格式

第一行五个整数 $N$ $A$ $B$ $C$ $D$。 第二行 $N$ 个整数 $s_1$ $s_2$ $\ldots$ $s_N$。

输出格式

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

样例 1

输入：

4 1 5 0 1
1 3 4 2

输出：

2

+-----+

|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

输入：

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

输出：

0

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

输入：

6 2 11 3 0
6 3 5 4 2 1

输出：

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|

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\%$ 的数据，$A$, $B$, $C$, $D$, $N\le 2000$。

对于所有数据，$1\le N\le 5\times10^5$，$1\le A, B\le 10^{12}$，$0\le C, D\le N$，$C+D\le N$。