• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

اگر دنباله‌ای از اعداد داشته باشید به اولین عدد طبیعی‌ای که در آن ظاهر نشده Mex آن دنباله می‌گوییم.
برای مثال Mex دنباله $(1, 2, 5, 9)$ برابر $3$ و Mex دنباله $(2, 5)$ برابر $1$ است.

دنباله $a_1, a_2, a_3,...,a_n\$ به شما داده شده است و باید جمع Mex تمام زیربازه‌های آن را به دست بیاورید. (در مجموع $\frac{n(n+1)}{2}$ زیربازه داریم.)

در واقع اگر $\ Mex_{i,j}$‌را برابر Mex زیر دنباله $(a_i,a_{i+1},...,a_j)\$ تعریف کنیم، شما باید مقدار زیر را چاپ کنید. $$\sum_{i=1}^{n}\ \sum_{j=i}^{n} Mex_{i,j}$$

ورودی

در سطر اول ورودی عدد $n$ و در سطر دوم $n$ عدد به شما داده می‌شود که عدد $i$-ام برابر عضو $i$ ام دنباله است.

$$1 \le n, a_i \le 100\ 000$$

خروجی

در تنها خط خروجی مقدار خواسته شده را نمایش دهید.

مثال

ورودی نمونه ۱

5
1 2 3 4 5

خروجی نمونه ۱

30

توضیح:

$Mex_{1,1} = 2$
$Mex_{1,2} = 3$
$Mex_{1,3} = 4$
$Mex_{1,4} = 5$
$Mex_{1,5} = 6$

و Mex زیربازه‌هایی که ۱ را ندارند برابر ۱ است.

ورودی نمونه ۲

8
2 1 4 2 1 3 2 1

خروجی نمونه ۲

113