HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Ближайший больший справа

Section problems

• Асимптотика
• Асимптотика
• Атбаш
• Багетная мастерская
• 1
• Банковский вклад
• Бинарная биржа
• Ближайшее число
• Ближайший больший справа
• Большее число
• Большее число
• Бонни и Клайд
• Босс
• 1
• Бронзовый призёр
• Будильник
• Бутерброд

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 4000/4000/4000/4000 ms. Memory limit 65536/65536/65536/65536 Kb.

Ближайший больший справа
Ближайший больший справа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив, элементами которого являются целые числа. Начальный элемент массива равен A0, а все остальные вычисляются по правилу (запись обозначает операцию взятия остатка от деления).

Для каждого элемента Ai требуется найти ближайший больший элемент справа. Другими словами, для каждого индекса i от 0 до N - 1 нужно найти такой минимальный индекс j > i, что Aj > Ai. Если справа от Ai нет бóльших элементов, то j =  - 1.

Входные данные

Первая строка содержит целое число N (1 ≤ N ≤ 5·106) — количество элементов массива.

Вторая строка содержит целые числа A0, X и Y (0 ≤ A0, X, Y ≤ 109) — соответственно начальный элемент массива и параметры для вычисления остальных элементов.

Выходные данные

Выведите одно целое число — сумму всех индексов j.

Примеры

Входные данные
5
1 1 1
Выходные данные
9
Входные данные
8
123456789 5 1
Выходные данные
24

Примечание

В первом примере рассматривается массив {1, 2, 3, 4, 5}, искомые индексы j = {1, 2, 3, 4,  - 1}.

Во втором примере рассматривается массив

{123456789, 617283946, 86419710, 432098551, 160492742, 802463711, 12318528, 61592641},

искомые индексы j = {1, 5, 3, 5, 5,  - 1, 7,  - 1}.

Для отправки решений необходимо выполнить вход.

www.contester.ru