ВКОШП: 2017/18

Саша готовится к олимпиадам по информатике и программированию и изучает структуры данных и задачи, с ними связанные. Одна из классических задач, которая попалась Саше, — поиск максимума на отрезке.

Эта задача заключается в следующем. Дан массив a из n целых чисел: a₁, a₂, ..., a_n. Требуется отвечать на запросы «найти максимум на отрезке элементов с i-го по j-й», то есть вычислить max {a_i, a_i + 1, ..., a_j}.

Конечно же, подобная задача не составила проблемы для Саши — вскоре была готова программа, которая отвечает на подобные запросы, да ещё и очень быстро. И тут выяснилось, что на разных отрезках результаты часто совпадают.

Теперь Сашу интересует, сколько же всего способов взять пару отрезков, чтобы эти отрезки не имели общих элементов, а максимумы значений элементов массива на этих двух отрезках совпадали.

Иначе говоря, требуется найти количество четвёрок i, j, k, l, таких, что 1 ≤ i ≤ j < k ≤ l ≤ n и max{a_i, a_i + 1, ..., a_j} = max{a_k, a_k + 1, ..., a_l}. Поскольку это количество может оказаться довольно большим, следует вывести остаток от деления этого числа на 1 000 000 007.