|
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 Выходные данные 9 Входные данные 8 Выходные данные 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}. Для отправки решений необходимо выполнить вход. |