+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقا فیروز که به‌دلیل قیمت بالای کیک، به تنگ آمده بود، تصمیم گرفت تا در شرکت تاکسیرانی تپ‌نپ کار کند. شهری که آقا فیروز در آن زندگی‌ می‌کند شامل $n$ میدان است که در یک خط راست قرار دارند و به ترتیب از چپ به راست با شماره‌های ۱ تا $n$ شماره‌گذاری شده‌اند و در وسط میدان شماره $i$، مجسمه‌ای با ارتفاع $h_i$ متر وجود دارد. هر مسافر در برنامه تپ‌نپ درخواستی به صورت $(i, j)$ می‌دهد و به این معنی است که می‌خواهد از میدان $i$ به میدان $j$ که $j < i$ است، برود. متاسفانه برنامه‌ی مسیریاب آقا فیروز خراب شده‌ و مسافرین باید به او آدرس بدهند. مسافر در هر مرحله یک عدد $k$ به آقا فیروز می‌گوید و او به سمت چپ حرکت می‌کند تا به **اولین** میدانی برسد که ارتفاع مجسمه‌اش دقیقا $k$ متر باشد. مسافر طوری عدد را می‌گوید که چنین میدانی در سمت چپ میدان فعلی و قبل از میدان $j - 1$ وجود داشته باشد. در نهایت وقتی مسافر به مقصد رسید، آقا فیروز به تعداد عددهایی که مسافر به او گفته‌‌، از او پول می‌گیرد و می‌دانیم مسافر‌ها به گونه‌ای آدرس می‌دهند که **کمترین پول** را به آقا فیروز بدهند. هم‌چنین آقا فیروز تا زمانی که یک مسافر را به مقصد نرسانده، او را پیاده نمی‌کند و در هر زمان **دقیقا یک مسافر** می‌تواند سوار ماشین شود. آقا فیروز که به پول نیاز دارد، می‌خواهد ببیند اگر به ازای هر $i$ و $j$ که $j < i$ است، درخواست $(i, j)$ را قبول کند، در مجموع چقدر پول بدست می‌آورد؛ اما بدلیل اینکه رانندگی انرژی زیادی از وی می‌گیرد، او از شما درخواست کرده‌ تا شما برایش این مقدار را حساب کنید. از آنجایی که ممکن است خروجی عددی بزرگ شود، جواب نهایی را به باقیمانده $10^9 + 7$ خروجی دهید. # ورودی در خط اول ورودی عدد $n$ می‌آید که بیانگر تعداد میدان‌های شهر است. در خط دوم به ترتیب $n$ عدد $h_1, h_2, h_3, \dots, h_n\ $ می‌آیند که $h_i$ برابر با ارتفاع مجسمه‌ای است که در میدان $i$ام قرار دارد. $$ 1 \le n \le 100\ 000 $$ $$ 1 \le h_i \le 100\ 000$$ # خروجی در تنها خط خروجی، مجموع پولی که آقا فیروز می‌تواند کسب کند را بگوید. # مثال ## ورودی نمونه ۱ ``` 3 4 1 2 ``` ## خروجی نمونه ۱ ``` 3 ``` درآمدی که آقا فیروز به ازای هر درخواست $(i, j)$ دارد به این‌صورت است: + (۲, ۱) = ۱ + (۳, ۱) = ۱ + (۳, ۲) = ۱ ## ورودی نمونه ۲ ``` 5 3 3 3 1 2 ``` ## خروجی نمونه ۲ ``` 17 ``` درآمدی که آقا فیروز به ازای هر درخواست $(i, j)$ دارد به این‌صورت است: + (۲, ۱) = ۱ + (۳, ۱) = ۲ + (۴, ۱) = ۳ + (۵, ۱) = ۳ + (۳, ۲) = ۱ + (۴, ۲) = ۲ + (۵, ۲) = ۲ + (۴, ۳) = ۱ + (۵, ۳) = ۱ + (۵, ۴) = ۱ <details class="blue"> <summary> راهنمایی ۱ </summary> مسئله را به شکل زیر به یک گراف $n$ راسی تبدیل می‌کنیم که هر راس نماینده یک میدان است. راس $i$ یالی مستقیم به راس $j$ دارد، اگر و تنها اگر $j<i$ و هیچ $k$ وجود نداشته باشد به صورتی که $j<k<i$ و $h_j=h_k$ باشد. در این صورت جواب مسئله برابر با جمع فاصله هر دو راس است. حال سعی می‌کنیم این مقدار را در گراف ساخته شده محاسبه کنیم. </details> <details class="blue"> <summary> راهنمایی ۲ </summary> یال‌ها را برعکس نگاه می‌کنیم. اگر $k$ کوچک‌ترین عددی باشد که $i<k$ و $h_i=h_k$ راس‌های $i+1$ تا $k$ به راس $i$ یال دارند و اگر $k$ وجود نداشته باشد راس‌های $i+1$ تا $n$ به راس $i$ یال دارند و اگر یال‌ها را برعکس کنیم راس $i$ به همه آن‌ها یال خواهد داشت. پس یعنی راس $i$ به تعدادی از راس‌های جلوی خود یال دارد. </details> <details class="blue"> <summary> راهنمایی ۳ </summary> تعریف می‌کنیم: $r_i$ یعنی جلوترین راسی که راس $i$ به آن یال دارد. در اصل راس $i$ به تمامی راس‌های $i+1$ تا $r_i$ فاصله یک دارد. ادعا می‌کنیم مسیر راس $i$ به راس‌های بزرگ‌تر از $r_i$ از راس $j$ می‌گذرد به صورتی که $i<j \le r_i$ و $r_j$ بیشینه است. </details> <details class="blue"> <summary> راهنمایی ۴ </summary> اولا که $r_i$ ها در واقع اولین مقدار بعد $i$ است که $a_r_i = a_i$ است. بعد از آن طبق ادعای بالا می‌توانیم اندیسی که در بالا گفته شده را با استفاده از سگمنت‌تری به دست آوریم. سپس از روی مجموع فاصله‌های آن اندیس، می‌توان فاصله‌های جدید را هم به دست آورد. </details>

حل سؤال در بانک سؤالات