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