Magic Sorter

You are given an array of N integers, a maximum number of passes K, and a swapping probability P. In each pass, the algorithm iterates over adjacent pairs in the array. If an element is greater than its next element, a swap is attempted with probability \(P\) (using the formula \(r = \frac{(1103515245 \times seed + 12345) \bmod 2^{31}}{2^{31}}\), where the initial seed is determined by the input parameters).

The process mimics a magical bubble-sort: if the array becomes sorted in non-decreasing order within the allowed K passes, output Yes; otherwise, output No.

Note: A custom deterministic random generator is used in order to make the process reproducible given the same input. The seed is computed as:

\(\text{seed} = (N \times 1000003 + K \times 10007 + \lfloor P\times1000 \rfloor + \sum_{i=1}^{N} array[i]) \bmod 2^{31}\)

inputFormat

The first line contains three space-separated values: an integer N (the number of elements), an integer K (the maximum number of passes), and a float P (the swapping probability).

The second line contains N space-separated integers representing the array.

outputFormat

Output a single word: Yes if the array can be sorted in non-decreasing order within K passes, or No otherwise.

4 10 1.0
4 3 2 1

Yes