Королевство Кремляндия представляет собой дерево (связный неориентированный граф без циклов), состоящее из \(n\) вершин. У каждой вершины \(i\) есть своя стоимость \(a_i\). Все вершины последовательно соединены рёбрами. Формально, для каждого \(1 \leq i < n\) существует ребро между вершинами \(i\) и \(i+1\).
Введём понятие функции \(f(l, r)\), принимающую два целых числа \(l\) и \(r\) (\(l \leq r\)):
- Оставим в дереве только вершины, стоимости которых находятся в пределах от \(l\) до \(r\).
- Значением функции будет количество компонент связности в новом графе.
Ваша задача состоит в том, чтобы посчитать следующую сумму: \(\)\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \(\)
Выходные данные
Выведите одно число — ответ на задачу.
Примечание
В первом примере значения функции будут такими:
- \(f(1, 1)=1\) (остается только вершина под номером \(2\), которая образует одну компоненту)
- \(f(1, 2)=1\) (остаются вершины \(1\) и \(2\), которые образуют одну компоненту)
- \(f(1, 3)=1\) (все вершины остаются, получается одна компонента)
- \(f(2, 2)=1\) (только вершина под номером \(1\))
- \(f(2, 3)=2\) (остаются вершины \(1\) и \(3\), которые образуют две компоненты)
- \(f(3, 3)=1\) (только вершина \(3\))
Суммарно выходит
\(7\).
Во втором примере значения функции будут такими:
- \(f(1, 1)=1\)
- \(f(1, 2)=1\)
- \(f(1, 3)=1\)
- \(f(1, 4)=1\)
- \(f(2, 2)=1\)
- \(f(2, 3)=2\)
- \(f(2, 4)=2\)
- \(f(3, 3)=1\)
- \(f(3, 4)=1\)
- \(f(4, 4)=0\) (никакой вершины не остаётся, а значит количество компонент равно \(0\))
Суммарно выходит
\(11\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 1 3
|
7
|
|
2
|
4
2 1 1 3
|
11
|
|
3
|
10
1 5 2 5 5 3 10 6 5 1
|
104
|