The 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$)  Totally out $7$.

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$)  Totally out $11$.

Difficulty: HARD
Tags: Dynamic programming

Combinatorics

Data structures

Mathematics
Skill types: Dynamic programming

Data structures

Starter code:

Solutions:
n = int(input())
vetor = list(map(int, input().split()))
vetor = [0] + vetor
resposta = 0
for i in range(1, n + 1):
	if vetor[i] > vetor[i - 1]:
		resposta += (vetor[i] - vetor[i - 1]) * (n - vetor[i] + 1)
	else:
		resposta += (vetor[i - 1] - vetor[i]) * vetor[i]
print(resposta)


n = int(input()) + 1
res = 0
a = tuple(map(int, input().split()))
for ai in a:
	res += ai * (n - ai)
for (ai, aj) in map(sorted, zip(a, a[1:])):
	res -= ai * (n - aj)
print(res)


import sys

class Main:

	def __init__(self):
		self.buff = None
		self.index = 0

	def __next__(self):
		if self.buff is None or self.index == len(self.buff):
			self.buff = sys.stdin.readline().split()
			self.index = 0
		val = self.buff[self.index]
		self.index += 1
		return val

	def next_int(self):
		return int(next(self))

	def solve(self):
		n = self.next_int()
		x = [self.next_int() for _ in range(0, n)]
		ans = 0
		for i in range(0, n):
			ans += x[i] * (n - x[i] + 1)
			if i > 0:
				ans -= min(x[i], x[i - 1]) * (n - max(x[i], x[i - 1]) + 1)
		print(ans)

def __starting_point():
	Main().solve()
__starting_point()


import sys
input = sys.stdin.readline
n = int(input())
A = [0] + list(map(int, input().split()))
ANS = 0
for i in range(1, n + 1):
	if A[i] > A[i - 1]:
		ANS += (n - A[i] + 1) * (A[i] - A[i - 1])
	else:
		ANS += A[i] * (A[i - 1] - A[i])
print(ANS)


n = int(input())
arr = [int(x) for x in input().split()]
arr.insert(0, 0)
resp = 0
for i in range(1, n + 1):
	if arr[i] > arr[i - 1]:
		resp += (arr[i] - arr[i - 1]) * (n - arr[i] + 1)
	if arr[i] < arr[i - 1]:
		resp += arr[i] * (arr[i - 1] - arr[i])
print(resp)


from math import sqrt, pow, ceil
from decimal import *
l1 = int(input())
l2 = input().split()
l2 = [int(i) for i in l2]
l2 = [0] + l2
ans = 0
for i in range(1, l1 + 1):
	ans += l2[i] * (l1 - l2[i] + 1)
for i in range(2, l1 + 1):
	ans -= (l1 - max(l2[i], l2[i - 1]) + 1) * min(l2[i], l2[i - 1])
print(ans)


def main():
	n = int(input())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	total = 0
	for i in range(1, n + 1):
		if a[i - 1] > a[i]:
			total += a[i] * (a[i - 1] - a[i])
		elif a[i - 1] < a[i]:
			total += (a[i] - a[i - 1]) * (n - a[i] + 1)
	print(total)
main()


n = int(input())
nS = [int(x) for x in input().split()]
nS.insert(0, 0)
answer = 0
for i in range(1, n + 1):
	if nS[i] > nS[i - 1]:
		answer += (nS[i] - nS[i - 1]) * (n - nS[i] + 1)
	else:
		answer += (nS[i - 1] - nS[i]) * nS[i]
print(answer)


__version__ = '1.0'
__date__ = '2019-04-20'
import sys

def count_contribution(n, ax, ay):
	if ay > ax:
		return (ay - ax) * (n - ay + 1)
	elif ay < ax:
		return ay * (ax - ay)
	else:
		return 0

def solve(n, a):
	result = a[0] * (n - a[0] + 1)
	for i in range(1, len(a)):
		result += count_contribution(n, a[i - 1], a[i])
	return result

def main(argv=None):
	n = int(input())
	a = list(map(int, input().split()))
	print(solve(n, a))
	return 0

def __starting_point():
	STATUS = main()
	return STATUS
__starting_point()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left, bisect_right
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]
MOD = 10 ** 9 + 7

def sum_evens(l, r):
	return pow(r, 2, MOD) - pow(l, 2, MOD) + r + l

def sum_odds(l, r):
	return pow(r, 2, MOD) - pow(l, 2, MOD) + 2 * l - 1

def solve():
	N = getInt()
	A = [0] + getInts()
	ans = 0
	for i in range(N):
		(a, b) = (A[i], A[i + 1])
		if a > b:
			ans += b * (a - b)
		else:
			ans += (b - a) * (N - b + 1)
	return ans
print(solve())


n = int(input())
a = [int(x) for x in input().split()]
s = 0
s = a[0] * (n - a[0] + 1)
for i in range(len(a) - 1):
	if a[i] < a[i + 1]:
		s += (a[i + 1] - a[i]) * (n - a[i + 1] + 1)
	elif a[i] > a[i + 1]:
		s += (a[i] - a[i + 1]) * a[i + 1]
print(s)


n = int(input())
a = [0] + list(map(int, input().split()))
ans = 0
for (i, j) in zip(a[:-1], a[1:]):
	if i < j:
		ans += (j - i) * (n - j + 1)
	else:
		ans += j * (i - j)
print(ans)


n = int(input())
d = list(map(int, input().split()))
a = [0]
a.extend(d)
an = 0
for i in range(n + 1):
	if a[i] > a[i - 1]:
		an += (a[i] - a[i - 1]) * (n - a[i] + 1)
	if a[i] < a[i - 1]:
		an += a[i] * (a[i - 1] - a[i])
print(an)


n = int(input())
a = [int(x) for x in input().split()]
ans = a[0] * (n - a[0] + 1)
for i in range(1, n):
	if a[i] > a[i - 1]:
		ans += (a[i] - a[i - 1]) * (n - a[i] + 1)
	elif a[i] < a[i - 1]:
		ans += a[i] * (a[i - 1] - a[i])
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
X = 0
for x in a:
	X += x * (n - x + 1)
Y = 0
for i in range(n - 1):
	(l, r) = (min(a[i], a[i + 1]), max(a[i], a[i + 1]))
	Y += l * (n - r + 1)
print(X - Y)


N = int(input())
arr = input()
arr = [int(x) for x in arr.split(' ')]
res = 0
for i in range(N):
	if i == 0:
		A = 0
		B = arr[i]
	else:
		A = arr[i - 1]
		B = arr[i]
	if A > B:
		res += B * (A - B)
	elif A < B:
		res += (B - A) * (N - B + 1)
print(res)


n = int(input())
l = input().split()
li = [int(i) for i in l]
li.insert(0, 0)
ans = 0
for i in range(1, n + 1):
	if li[i] >= li[i - 1]:
		ans = ans + (li[i] - li[i - 1]) * (n - li[i] + 1)
	else:
		ans = ans + li[i] * (li[i - 1] - li[i])
print(ans)


n = int(input())
A = input().split()
pop = 0
ans = 0
for i in range(0, n):
	cur = int(A[i])
	if pop > cur:
		ans += cur * (pop - cur)
	elif pop < cur:
		ans += (cur - pop) * (n - cur + 1)
	pop = cur
print(ans)


n = int(input())
v = [0] + [int(e) for e in input().split()]
ans = 0
for (a, b) in zip(v[:-1], v[1:]):
	if a < b:
		ans += (b - a) * (n - b + 1)
	else:
		ans += b * (a - b)
print(ans)


import sys
n = int(sys.stdin.readline().strip())
a = list(map(int, sys.stdin.readline().strip().split()))
s = a[0] * (n - a[0] + 1)
for i in range(1, n):
	if a[i - 1] < a[i]:
		s = s + (a[i] - a[i - 1]) * (n - a[i] + 1)
	if a[i - 1] > a[i]:
		s = s + a[i] * (a[i - 1] - a[i])
print(s)


n = int(input())
arr = list(map(int, input().split()))
ans = 0
ans += arr[0] * (n - arr[0] + 1)
for i in range(1, n):
	if arr[i - 1] < arr[i]:
		ans += (arr[i] - arr[i - 1]) * (n - arr[i] + 1)
	if arr[i - 1] > arr[i]:
		ans += arr[i] * (arr[i - 1] - arr[i])
print(ans)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
import threading
from collections import defaultdict
threading.stack_size(10 ** 8)
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
sys.setrecursionlimit(300000)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
n = int(input())
l = list(map(int, input().split()))
x = l[0] - 1
y = n - l[0]
ans = n * (n + 1) // 2 - x * (x + 1) // 2 - y * (y + 1) // 2
for i in range(1, n):
	if l[i] > l[i - 1]:
		ans += (n - l[i] + 1) * (l[i] - l[i - 1])
	else:
		ans += l[i] * (l[i - 1] - l[i])
print(ans)


n = int(input())
num = input().split()
num = [int(x) for x in num]
num = [0] + num
par = 0
for i in range(1, len(num)):
	if num[i - 1] < num[i]:
		par += (num[i] - num[i - 1]) * (n - num[i] + 1)
	if num[i - 1] > num[i]:
		par += num[i] * (num[i - 1] - num[i])
print(par)


n = int(input())
t = input().split()
t[0] = int(t[0])
s = t[0] * (n - t[0] + 1)
for i in range(1, n):
	t[i] = int(t[i])
	if t[i] > t[i - 1]:
		s = s + (t[i] - t[i - 1]) * (n - t[i] + 1)
	else:
		s = s + t[i] * (t[i - 1] - t[i])
print(s)


n = int(input())
a = [0]
b = [int(i) for i in input().split()]
a += b
ans = 0
for i in range(1, n + 1):
	if a[i - 1] < a[i]:
		ans += (a[i] - a[i - 1]) * (n - a[i] + 1)
	else:
		ans += a[i] * (a[i - 1] - a[i])
print(ans)


n = int(input())
nums = list(map(int, input().split()))
ans = nums[0] * (n - nums[0] + 1)
for i in range(1, n):
	if nums[i] > nums[i - 1]:
		ans += (nums[i] - nums[i - 1]) * (n - nums[i] + 1)
	elif nums[i] < nums[i - 1]:
		ans += (nums[i - 1] - nums[i]) * nums[i]
print(ans)


N = int(input())
A = [0] + [int(e) for e in input().split()]
ans = 0
for i in range(1, N + 1):
	if A[i] > A[i - 1]:
		ans += (A[i] - A[i - 1]) * (N - A[i] + 1)
	else:
		ans += A[i] * (A[i - 1] - A[i])
print(ans)


def in_int():
	return int(input())

def in_list():
	return [int(x) for x in input().split()]
n = in_int()
ns = in_list()
ans = 0
for i in range(n - 1):
	(a, b) = (ns[i], ns[i + 1])
	if a > b:
		ans += (a - b) * (n - a + 1)
	else:
		ans += a * (b - a)
a = ns[-1]
ans += a * (n - a + 1)
print(ans)


n = int(input())
arr_a = [int(a) for a in input().split()]
result = 0
for a in arr_a:
	temp = a * (n - a + 1)
	result += temp
i = 1
while i < n:
	tempMin = min(arr_a[i], arr_a[i - 1])
	tempMax = n - max(arr_a[i], arr_a[i - 1]) + 1
	result -= tempMin * tempMax
	i += 1
print(result)


N = int(input())
A = [int(a) for a in input().split()]

def calc(a0, b0):
	(a, b) = (min(a0, b0), max(a0, b0))
	return b - 1 + (a - 1) * (b - a - 1) + N - a + (b - a - 1) * (N - b)

def calc0(a):
	return N + (a - 1) * (N - a)
s = calc0(A[0]) + calc0(A[-1])
for i in range(N - 1):
	s += calc(A[i], A[i + 1])
print(s // 2)


n = int(input())
a = list(map(int, input().split()))
ans = n * n * (n + 1) // 2
rd = 0
for i in range(n - 1):
	l = min(a[i], a[i + 1])
	r = max(a[i], a[i + 1])
	rd += l * (n - r + 1)
for i in range(n):
	rd += max((a[i] - 2) * (a[i] - 1) // 2, 0)
	rd += n - 1
	rd += (n - a[i]) * (n - a[i] - 1) // 2
ans -= rd
print(ans)


n = int(input())
a = list(map(int, input().split()))
ans = a[0] * (n - a[0] + 1)
for i in range(1, n):
	if a[i - 1] == a[i]:
		continue
	elif a[i - 1] < a[i]:
		ans += (a[i] - a[i - 1]) * (n - a[i] + 1)
	elif a[i - 1] > a[i]:
		ans += a[i] * (a[i - 1] - a[i])
print(ans)


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
b = []
for x in a:
	if not b or b[-1] != x:
		b.append(x)
p = defaultdict(list)
for i in range(len(b)):
	p[b[i]].append(i)
ans = cur = 0
for r in range(1, n + 1):
	for i in p[r]:
		cur += r
		if len(b) == 1:
			pass
		elif i == 0:
			if b[i + 1] < b[i]:
				cur -= b[i + 1]
		elif i == len(b) - 1:
			if b[i - 1] < b[i]:
				cur -= b[i - 1]
		else:
			mx = max(b[i - 1], b[i + 1])
			mn = min(b[i - 1], b[i + 1])
			if mx < b[i]:
				cur -= mx + mn
			elif mn < b[i]:
				cur -= mn
	ans += cur
print(ans)