- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
امین بعد از یک روز طولانی، تصمیم گرفته که از سرزمین پردیس کد فرار کند و به استراحت بپردازد. ولی رومینا متوجه شده و میخواهد مانع فرار او شود. اما امین پیشنهاد میدهد که یک مسأله حل کند و بگذارند که برود.
در ابتدا یک جایشگت روی تخته نوشته شده است. رومینا در هر مرحله یک دنباله جدید روی تخته مینویسد و دنباله قبلی را پاک میکند. دنباله جدید را به این صورت مینویسد که زیر هر دو عدد متوالی:
- اگر تعداد اعضا دنبالهی فعلی روی تخته فرد باشد، عدد بزرگتر را انتخاب میکند و پایین آنها در دنباله جدید مینویسد.
- اگر تعداد اعضا دنبالهی فعلی روی تخته زوج باشد، عدد کوچکتر را انتخاب میکند و پایین آنها در دنباله جدید مینویسد.
به همین ترتیب بعد از عملیاتهای رومینا در هر مرحله یک دنباله جدید با یک عضو کمتر روی تخته نوشته شده و سپس دنباله قبلی پاک میشود. این مراحل انقدر تکرار میشوند تا یک عدد روی تخته باقی بماند.
حالا برای رومینا سوال شده است که اگر به ازای همه ی دنبالههای مختلفی که از پاک کردن قسمتی از سمت راست و قسمتی از سمت چپ دنباله اولیه بدست میآیند، بازی را شروع کند و عدد باقی مانده را در دفترش بنویسد. مجموع تمام اعداد نوشته شده در دفترش چند میشود؟
به امین کمک کنید مسأله را حل کند تا بتواند استراحت کند. البته چون مجموع ممکن است زیاد باشد، باقی مانده آن را به \( 10^9 + 7\) چاپ کنید.
ورودی
خط اوّل شامل یک عدد صحیح \(n\) است که نشاندهنده تعداد اعضای جایگشت اولییه است.
\[ 1 \leq n \leq 2 \times 10^5 \]
سپس در خط بعدی \(n\) عدد که به ترتیب از چپ به راست ترتیب اعضای جایگشت هستند ورودی داده میشود. \[ 1 \le a_i \le n \] تضمین میشود که دنباله ابتدایی جایگشت است و عدد تکراری ندارد.
خروجی
باقی مانده مجموع تمام جوابها به ازای تمام زیر رشتههای جایگشت اولیه را به \(10^9+7\) چاپ کنید.
مثال
ورودی نمونه ۱
5
1 2 3 4 5
خروجی نمونه ۱
42
ورودی نمونه ۲
4
1 3 2 4
خروجی نمونه ۲
23