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

---

اگر دنباله‌ای از اعداد داشته باشید به اولین عدد طبیعی‌ای که در آن ظاهر نشده 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