E. Количество компонент
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Королевство Кремляндия представляет собой дерево (связный неориентированный граф без циклов), состоящее из $$$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) $$$$$$

Входные данные

Первая строка содержит одно целое число $$$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
Примечание

В первом примере значения функции будут такими:

  • $$$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$$$.