- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
آقا فیروز که بهدلیل قیمت بالای کیک، به تنگ آمده بود، تصمیم گرفت تا در شرکت تاکسیرانی تپنپ کار کند. شهری که آقا فیروز در آن زندگی میکند شامل \(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)\) دارد به اینصورت است:
- (۲, ۱) = ۱
- (۳, ۱) = ۲
- (۴, ۱) = ۳
- (۵, ۱) = ۳
- (۳, ۲) = ۱
- (۴, ۲) = ۲
- (۵, ۲) = ۲
- (۴, ۳) = ۱
- (۵, ۳) = ۱
- (۵, ۴) = ۱