Problem Description

Translated from COCI 2009.10 T5 “GENIJALAC”.

Mirko invented a shuffling machine. The machine takes a paper tape with $N$ columns and infinitely many rows as both input and output. These $N$ columns are numbered $1 \ldots N$ in order.

At the beginning, only the first row of the tape contains numbers, and every row below it is blank.
In the first row, each column contains an integer: column $i$ contains the integer $i$.
In addition, Mirko is given a shuffle permutation, which is a permutation of length $N$: $s_1,$ $s_2,$ $\ldots,$ $s_N$.

There is a row pointer, which initially points to the first row.
Each time the machine runs, for every $i$, it moves the number in column $i$ of the current row (the row pointed to by the pointer) to column $s_i$ of the next row. After all $N$ numbers are placed, the pointer moves down by one row.

Mirko runs the machine infinitely many times. Now Mirko cuts off the first $C$ columns and the last $D$ columns of the tape; we call the result the new tape.

Question: among rows $A \sim B$ of the new tape, how many rows are identical to the first row of the new tape?

Input Format

The first line contains five integers $N, A, B, C, D$.
The second line contains $N$ integers $s_1,$ $s_2,$ $\ldots,$ $s_N$.

Output Format

One line with one integer: the number of rows among rows $A \sim B$ of the new tape that are identical to the first row of the new tape.

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

Hint

Sample Explanation 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

Sample Explanation 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

Sample Explanation 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|
     +-----+

Constraints and Hints

For $40\%$ of the testdata, $A,$ $B,$ $C,$ $D,$ $N \le 2000$.
For all testdata, $1 \le N \le 5 \times 10^5,$ $1 \le A, B \le 10^{12},$ $0 \le C,$ $D \le N,$ and $C + D \le N$.

Translated by ChatGPT 5