|
Дана последовательность целых чисел. Инверсией назовём такую ситуацию,
когда большее число стоит впереди меньшего.
Например, в последовательности 4 3 2 5 1
всего 7 инверсий: 4 и 3, 4 и 2, 4 и 1, 3 и 2, 3 и 1, 2 и 1, 5 и 1.
Требуется определить количество инверсий в последовательности.
Входная последовательность определяется следующим образом: задаётся количество элементов N,
первый член a1, а также параметры P и Q. Каждый следующий член последовательности
вычисляется по формуле:
ai = (P * ai-1 + Q) mod 231
Input
Четыре целых числа N, a1, P и Q.
Ограничения: 1 ≤ N ≤ 107, 0 ≤ a1, P, Q < 231.
Output
Выведите одно целое число - количество инверсий.
Sample
| Input | Output |
|---|
|
5 3 64525 1013904223
|
2 |
Comments
Пояснение к примеру: входные данные задают последовательность 3 1014097798 1847565613 1925331624 1107906023
Примечание: в данной задаче разрешается использовать многопоточность, вам доступно 4 процессора.
|
