+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- اگر دنباله‌ای از اعداد داشته باشید به اولین عدد طبیعی‌ای که در آن ظاهر نشده _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 ``` -------------- <details class="blue"> <summary> راهنمایی ۱ </summary> فرض کنید برای هر پیشوند از ارایه *Mex* را به دست آوردید. حالا عنصر اول را حذف کنید و *Mex* هر پیشوند را حساب کنید. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> بعد از حذف عنصر اول، پیشنود‌هایی که *Mex* آن کمتر از $a_1$ بودند تغییری نمی‌کنند. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> بعد از حذف عنصر اول در صورتی که _Mex_ پیشنوندی قرار باشد تغییر کند، مقدار آن برابر $a_1$​ می‌شود. </details> <details class="blue"> <summary> راه حل </summary> اگر $m_i$ برابر *Mex* پیشوندی باشد که به *i* ختم می شود. می‌توانید مشاهده کنید که دنباله زیر صعودی است: $$ m_1 \le m_2 \le m_3 \le ... \le m_n$$ و وقتی عنصر اول را حذف می‌کنید، اگر دومین تکرار این عنصر در اندیس *x* باشد. (یعنی $a_1= a_x$) برای هر $1 \le i \lt x$ مقدار $m_i$ ممکن است عوض شود و بقیه تغییری نمی‌کنند چون قبلا در خانه اول $a_1$ وجود داشته و تمام پیشوند‌هایی که از خانه *x* رد می‌شودند هنوز $a_1$ را دارند. و از طرفی برای هر کدام از آن *i*ها مقدار $m_i$ مینیمم گرفته می‌شود با $a_1$ چون ممکن است این عنصر اولین کسی باشد که دیگر در بازه نیست. پیاده سازی الگوریتم با درخت سگمنت یا *BST* امکان پذیر است. </details>