AvaSE-JAN-2018

Start

2018-01-13 23:59 CET

AvaSE-JAN-2018

End

2018-01-27 23:59 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -10 days 0:57:40

Time elapsed

240:57:40

Time remaining

95:02:20

Problem D
Genijalac

Mirko is a genius. But the purpose of his inventions is not always obvious. His latest invention, the Shuffle-o-matic 3175, is one of those. The Shuffle-o-matic is used in a very special way. First Mirko places $N$ paper cards, with numbers 1 to $N$ printed on them, on the Shuffle-o-matic working surface. Then he inputs the shuffle sequence in the special input console and hits the go button. The machine than reads the paper cards and outputs the read sequence of numbers on its output tape. It than shuffles the cards according to the shuffle sequence. After that it reads the newly obtaind sequence and writes it onto a new line on its output tape. Then it procedes to shuffle the cards again acording to the same shuffle sequence, scans and writes the output to the tape. The machine does this until it runs out of tape.

After experimenting with the machine Mirko decided to rest a bit on the floor. There he noticed a piece of output tape. The piece is neatly cut just before the $A$-th output row and just after the $B$-th output row. It is also missing the first $C$ numbers and the last $D$ numbers in all rows.

He now wonders how many rows on that piece of paper have the property that all numbers in the row, that are still on the paper, are in the exact same spot they were before all the shuffling began.

Case 1

Shuffle-o-matic outputs:
1 2 3 4
1 3 4 2
1 2 3 4
1 3 4 2
1 4 2 3
1 2 3 4

Mirko finds:
1 2 3
1 3 4
1 4 2
1 2 3
1 3 4

The first and fourth rows are interesting to Mirko.

Case 2

Shuffle-o-matic outputs:
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

Case 3

Shuffle-o-matic outputs:
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

Figure 1: Sample tests description

Input

The first line of input contains integers $N$, $A$, $B$, $C$ and $D$ in that order ($1 \leq N \leq 500\, 000$, $A \leq B \leq 10^{12}$, $0 \leq C, D \leq N$, $C + D < N$).

The second line contains the shuffle sequence. The sequence is given as a permutation of numbers 1 to $N$. If the $k$-th number in the shuffle sequence is $x$, after each shuffle the $k$-th element in the resulting sequence is the $x$-th element in the previous sequence.

Output

In the first and only line of input print the number of rows that have the property Mirko is looking for.

Sample Input 1 Sample Output 1
4 1 5 0 1
1 3 4 2
2
Sample Input 2 Sample Output 2
7 3 8 1 2
2 3 1 6 4 7 5
0
Sample Input 3 Sample Output 3
6 2 11 3 0
6 3 5 4 2 1
1