### Problem Statement

Bubble-sort is a well-known sorting algorithm, although not a very efficient one. In each iteration of bubble-sort, the algorithm works from start to end along a list, comparing each pair of adjacent elements. If the adjacent elements are out of order, then they are swapped. If no elements are swapped in an iteration, then the list is sorted and the algorithm terminates; otherwise, the algorithm continues with another iteration. In order to analyze the performance of bubble-sort, you want to determine how many iterations are required to sort a given list in non-decreasing order. The list might be quite large, so it will be codified in the following way. You will be given int[]s X and Y, and ints L0, M, and n. Generate the list L of length n using the following pseudo-code. Array indices are 0-based.
```L = L0
for i := 1 to n-1
L[i] = (L[i-1] * X[i % length(X)] + Y[i % length(Y)]) MOD M
```
You must calculate the number of iterations required to bubble-sort L in non-decreasing order.

### Definition

 Class: BubbleSortIterations Method: numIterations Parameters: int[], int[], int, int, int Returns: int Method signature: int numIterations(int[] X, int[] Y, int L0, int M, int n) (be sure your method is public)

### Notes

-The input is encoded purely for convenience. The intended solution does not rely on any properties of the way it is generated, and will work for any list L.

### Constraints

-X and Y will each contain between 1 and 50 elements, inclusive.
-Each element of X and Y will be between 0 and M-1, inclusive.
-L0 will be between 0 and M-1, inclusive.
-M will be between 1 and 1,000,000, inclusive.
-n will be between 1 and 100,000, inclusive.

### Examples

0)

 `{0}` `{10, 1, 5, 2, 3}` `10` `100` `5`
`Returns: 3`
 The generated sequence is 10, 1, 5, 2, 3. After one iteration it is 1, 5, 2, 3, 10. After two it is 1, 2, 3, 5, 10. The third iteration detects that the sequence is now sorted.
1)

 `{0}` `{1, 3, 5, 7, 9}` `1` `100` `5`
`Returns: 1`
 The generated sequence is 1, 3, 5, 7, 9. The sequence is already sorted, but one iteration is required to detect this.
2)

 `{999998}` `{500000}` `500000` `1000000` `100`
`Returns: 1`
 Be careful not to overflow when generating L.
3)

 `{234, 56, 567, 3147, 23464, 57128, 1254, 45, 23247, 1347, 145, 123}` `{3413, 171, 58, 569, 40, 467, 2456, 246, 2684, 5, 61, 8, 258, 24524, 2, 58, 245, 674}` `1` `99991` `100000`
`Returns: 99228`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7854

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10770&pm=7854

bmerry

#### Testers:

PabloGilberto , brett1479 , Olexiy , ivan_metelsky

Sorting