该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

You are given a positive integer k and k positive integers a0, a1, ..., ak−1.

Then three positive integers n, m, x are given.

Let b0, b1...bn be the following sequence of n numbers:

Find the number of i(0 ≤ i < n) such that (bi mod m) ≤ (bi+1 mod m).

Format

Input

The first line contains an integer k (1 ≤ k ≤ 106 ).

The second line contains k integers a0, a1, ..., ak−1 (1 ≤ ai ≤ 109 ).

The third line contains three integers n, m, x (1 ≤ n ≤ 109 , 1 ≤ m ≤ 109 , 1 ≤ x ≤ 109 ).

Output

Output a single integer, denoting the answer.

Samples

3
2 4 3
4 7 5

2

Note

b0 = 5, b1 = b0 + a0 = 7, b2 = b1 + a1 = 11, b3 = b2 + a2 = 14, b4 = b3 + a0 = 16

b1 mod 7 = 0 ≤ 4 = b2 mod 7

b3 mod 7 = 0 ≤ 2 = b4 mod 7

Limitation

Input file:

standard input

Output file:

standard output

Time limit: 1 second

Memory limit: 512 megabytes