Задача №115438. Кошмарная сумма
Дан массив \(a\) длины \(n\), состоящий из различных положительных целых чисел. Вычислите
\(\)\sum\limits_{l=1}^{n} \sum\limits_{r=l}^{n} \left\lfloor\frac{\max(a_{l},a_{l+1},\ldots,a_{r})}{\min(a_{l},a_{l+1},\ldots,a_{r})}\right\rfloor\(\)
Здесь \(\lfloor x \rfloor\) означает \(x\), округленный вниз до ближайшего целого.
Таким образом, необходимо вычислить сумму результатов целочисленного деления максимума на минимум по всем подотрезкам массива \(a\).
В первой строке ввода находится единственное целое число \(n\) — длина массива \((1 \leq n \leq 300\,000)\).
Во второй строке ввода находятся \(n\) целых чисел — массив \(a\) \((1 \leq a_{i} \leq 300\,000)\).
Гарантируется, что все числа в массиве \(a\) различны.
Выведите единственное число — искомую сумму.
Рассмотрим пример подробнее:
| \([l, r\)] | \(a[l\ldots r]\) | \(\min\) | \(\max\) | \(\left\lfloor\frac{\max}{\min}\right\rfloor\) |
| \([1, 1]\) | \([1]\) | \(1\) | \(1\) | \(1\) |
| \([1, 2]\) | \([1 ,3]\) | \(1\) | \(3\) | \(3\) |
| \([1, 3]\) | [\(1, 3, 6]\) | \(1\) | \(6\) | \(6\) |
| \([1, 4]\) | [\(1, 3, 6, 4]\) | \(1\) | \(6\) | \(6\) |
| \([1, 5]\) | [\(1, 3, 6, 4, 2]\) | \(1\) | \(6\) | \(6\) |
| \([1, 6]\) | [\(1, 3, 6, 4, 2, 5]\) | \(1\) | \(6\) | \(6\) |
| \([2, 2]\) | \([3]\) | \(3\) | \(3\) | \(1\) |
| \([2, 3]\) | \([3, 6]\) | \(3\) | \(6\) | \(2\) |
| \([2, 4]\) | \([3, 6, 4]\) | \(3\) | \(6\) | \(2\) |
| \([2, 5]\) | \([3, 6, 4, 2]\) | \(2\) | \(6\) | \(3\) |
| \([2, 6]\) | \([3, 6, 4, 2, 5]\) | \(2\) | \(6\) | \(3\) |
| \([3, 3]\) | \([6]\) | \(6\) | \(6\) | \(1\) |
| \([3, 4]\) | \([6, 4]\) | \(4\) | \(6\) | \(1\) |
| \([3, 5]\) | \([6, 4, 2]\) | \(2\) | \(6\) | \(3\) |
| \([3, 6]\) | \([6, 4, 2, 5]\) | \(2\) | \(6\) | \(3\) |
| \([4, 4]\) | \([4]\) | \(4\) | \(4\) | \(1\) |
| \([4, 5]\) | \([4, 2]\) | \(2\) | \(4\) | \(2\) |
| \([4, 6]\) | \([4, 2, 5]\) | \(2\) | \(5\) | \(2\) |
| \([5, 5]\) | \([2]\) | \(2\) | \(2\) | \(1\) |
| \([5, 6]\) | \([2, 5]\) | \(2\) | \(5\) | \(2\) |
| \([6, 6]\) | \([5]\) | \(5\) | \(5\) | \(1\) |
6 1 3 6 4 2 5
56