Сумма максимальных и минимальных значений для всех подмассивов

Question

Мы хотим узнать сумму максимальных и минимальных значений для всех подмассивов в массиве.
Например:
Вход: [1,2]
Выход: 1 (3 подмассива с [1,2], имеющим 1 как разность = 1)

Объяснение вывода:
Подмассивы: [1] [1,2] [2]
Разница: 0, 1, 0
Итак, ответ: 1

Наивное решение проблемы имеет временную сложность O(n^2).
Есть ли какое-нибудь решение в O(n) или, возможно, меньшее, чем наивное.