نقاشی (Painting)

پخمه در حال کشیدن یک نقاشی از ساختمان‌های شهر است. این نقاشی را می‌توان به صورت یک آرایه‌ی $a$ به طول $n$ توصیف کرد که $a_i$ برابر ارتفاع ساختمان $i$اُم است. می‌دانیم ‌که ساختمان‌های کشیده شده در ابتدا متعادل هستند؛ یعنی اختلاف ارتفاع هر دو ساختمان مجاور دقیقاً یک است.

پخمه ارزش یک بازه از ساختمان‌هایی که کشیده را برابر جمع ارتفاع ساختمان‌های این بازه در نظر می‌گیرد. از طرف دیگر، پخمه به یک بازه از ساختمان‌ها، نیمه متعادل می‌گوید اگر و تنها اگر ارتفاع هر دو ساختمان متوالی، حداکثر یک واحد اختلاف داشته باشد.

پخمه حالت آرمانی یک زیر‌بازه از نقاشی‌اش را حالتی می‌نامد که ارتفاع سر و ته این زیربازه از نقاشی او ثابت مانده‌ باشد و همچنین ارتفاع ساختمان‌های میانی به طوری تغییر کرده باشد که ارزش این بازه بیشینه مقدار ممکن را به خود گرفته باشد و در عین حال، ارتفاع ساختمان‌ها نیمه متعادل باقی‌ مانده باشد.

پخمه که از نقاشی زیبای خود به وجد آمده، از شما می‌خواهد که به ازای هر زیربازه از نقاشی‌اش، ارزش حالت آرمانی این زیربازه را محاسبه کنید و در نهایت باقی‌مانده حاصل جمع این مقادیر را بر $10^9 + 7$ به او اطلاع دهید.

خط اول شامل عدد $n$ است که نشان‌دهنده‌ی تعداد ساختمان‌های شهر است.

در خط بعدی $n$ عدد که با فاصله جدا شده‌اند داده می‌شود که عدد $i$اُم نشان‌دهنده‌ی $a_i$ است.

تضمین می‌شود که اعداد آرایه‌ی ورودی متعادل هستند.

در تنها خط خروجی، جمع ارزش تمام زیر‌بازه‌ها را در حالت آرمانی را محاسبه کرده و باقی‌مانده این مقدار بر $10^9 + 7$ را خروجی دهید.

• زیرمسئله اول (۶ نمره): $n \leq 500$
• زیرمسئله دوم (۲۱ نمره): $n \leq 5\times10^3$
• زیرمسئله سوم (۱۳ نمره): $1 \leq a_i \leq 2$
• زیرمسئله چهارم (۴۶ نمره): $1 \leq n \leq 2\times10^5$
• زیرمسئله پنجم (۱۴ نمره): بدون محدودیت اضافی

• $1 \leq n \leq 10^6$
• $1 \leq a_i \leq 10^6$
• $(2 \leq i \leq n) \quad |a_i - a_{i - 1}| = 1$

در ورودی اول، بازه‌های به طول یک و دو تغییری نخواهند کرد و حداکثر ارزش آن‌ها برابر جمع اولیه‌شان است. در نتیجه مجموع ارزش این بازه‌ها ۲۳ است. مجموع ارزش بازه‌های به طول ۳ برابر ۱۷ است:

• بازه‌ی $[3, 2, 1]$: این بازه تغییری نمی‌کند (در حالت آرمانی‌ است) و ارزش آن $3+2+1=6$ است.
• بازه‌ی $[2, 1, 2]$: در این بازه می‌توانیم عدد وسط را به ۳ تغییر دهیم و ارزش آن $2+3+2=7$ است.
• بازه‌ی $[1, 2, 1]$:‌ این بازه نیز تغییری نمی‌کند و ارزش آن $1+2+1=4$ است.

مجموع ارزش بازه‌های به طول ۴ برابر ۲۰ است:

• بازه‌ی $[3, 2, 1, 2]$: در این بازه فقط می‌توانیم دو عدد میانی را تغییر دهیم. با این کار می‌توانیم به آرایه‌ی $[3, 4, 3, 2]$ برسیم که ارزش آن برابر ۱۲ است.
• بازه‌ی $[2, 1, 2, 1]$: این آرایه را نیز می‌توانیم به $[2, 3, 2, 1]$ تبدیل کنیم که ارزش آن برابر ۸ است.

در تنها بازه‌ی به طول ۵ نیز که برابر آرایه‌ی اصلی است، تنها می‌توانیم ۳ عدد میانی را تغییر دهیم که می‌توانیم با تغییر دو عدد اول به آرایه‌ی $[3, 4, 3, 2, 1]$ برسیم که ارزش آن برابر ۱۳ است. در نتیجه مجموع ارزش تمام بازه‌ها برابر $23+17+20+13=73$ است.

در ورودی دوم، تمام بازه‌های آرایه بیش‌ترین ارزش ممکن خود را دارند و می‌توان نشان داد که هیچ کدام از بازه‌ها را نمی‌توان به گونه‌ای تغییر داد که اعدادش نیمه متعادل بمانند و مجموعشان بیش‌تر شود. در نتیجه پاسخ برابر جمع اعداد تمام زیربازه‌های آرایه است که برابر ۵۰ می‌شود.