Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Number of Components

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe Kingdom of Kremland is a tree (a connected undirected graph without cycles) consisting of $$$n$$$ vertices. Each vertex $$$i$$$ has its own value $$$a_i$$$. All vertices are connected in series by edges. Formally, for every $$$1 \leq i < n$$$ there is an edge between the vertices of $$$i$$$ and $$$i+1$$$.

Denote the function $$$f(l, r)$$$, which takes two integers $$$l$$$ and $$$r$$$ ($$$l \leq r$$$):

- We leave in the tree only vertices whose values range from $$$l$$$ to $$$r$$$.
- The value of the function will be the number of connected components in the new graph.

Your task is to calculate the following sum: $$$$$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) $$$$$$

Input

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of vertices in the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — the values of the vertices.

Output

Print one number — the answer to the problem.

Examples

Input

3 2 1 3

Output

7

Input

4 2 1 1 3

Output

11

Input

10 1 5 2 5 5 3 10 6 5 1

Output

104

Note

In the first example, the function values will be as follows:

- $$$f(1, 1)=1$$$ (there is only a vertex with the number $$$2$$$, which forms one component)
- $$$f(1, 2)=1$$$ (there are vertices $$$1$$$ and $$$2$$$ that form one component)
- $$$f(1, 3)=1$$$ (all vertices remain, one component is obtained)
- $$$f(2, 2)=1$$$ (only vertex number $$$1$$$)
- $$$f(2, 3)=2$$$ (there are vertices $$$1$$$ and $$$3$$$ that form two components)
- $$$f(3, 3)=1$$$ (only vertex $$$3$$$)

In the second example, the function values will be as follows:

- $$$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$$$ (there is no vertex left, so the number of components is $$$0$$$)

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2019 13:14:15 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|