- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
«مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینهی بحران محیط زیست استفاده کند؛ امّا...
حتما داستان هنرنمایی لیته و فیته بر روی صحنه را به یاد دارید. اکنون، مدّت زیادی از آن هنرنمایی میگذرد و لیته و فیته حسابی هنرمندان ماهری شدهاند.
مسریکس همراه با باقر و بیقر، دو نفر از دوستانش، برای تماشای هنرنمایی جدید لیته و فیته به سالن تئاتر رفته است. در همان لحظه فکری هوشمندانه به ذهن مسریکس میرسد و به باقر و بیقر میگوید هر کدام دو صندلی خالی از دو ردیف مختلف سالن تئاتر انتخاب کنند. به عبارت دیگر، باقر باید یک ردیف را انتخاب کند و سپس از آن ردیف دو صندلی خالی انتخاب کند. سپس بیقر باید یک ردیف دیگر را انتخاب کرده و دو صندلی خالی از آن ردیف انتخاب کند.
در سالن تئاتر \(n\) صندلی خالی وجود دارد. فرض کنید باقر صندلیهای شمارهی \(t_1\) و \(t_2\) را از سطر \(r_1\) انتخاب کند و بیقر صندلیهای شمارهی \(s_1\) و \(s_2\) را از سطر \(r_2\) انتخاب کند.
این ۴ صندلی را باقرپسند میگوییم اگر ۲ شرط زیر به ازای آنها برقرار باشد.
- \(r_1 < r_2\)
- \(t_1 < s_1 < t_2 < s_2\)
و آنها را بیقرپسند میگوییم اگر ۲ شرط زیر به ازای آنها برقرار باشد.
- \(r_1 < r_2\)
- \(s_1 < t_1 < s_2 < t_2\)
مسریکس میخواهد «تعداد حالاتی که ۴ صندلی انتخاب شده بیقرپسند باشند» منهای «تعداد حالاتی که ۴ صندلی انتخاب شده باقرپسند باشند» را محاسبه کند تا بر اساس آنها راهکاری برای بحران محیط زیست پیدا کند. لطفا باقیماندهی این مقدار به \(1\ 000\ 000\ 007\) را برای مسریکس محاسبه کنید.
برای راحتی فرض کنید سالن تئاتر متشکّل از \(n\) ستون است و در هر ستون دقیقا یک صندلی خالی وجود دارد. شمارهی ردیف صندلی خالیای که در ستون \(i\)ام قرار دارد برابر با \(a_i\) است.
ورودی
در سطر اوّل ورودی عدد \(n\) آمده است.
در سطر دوم \(n\) عدد آمده است که نشاندهندهی آرایهی \(a\) هستند.
\[1 \le n \le 100\ 000\] \[1 \leq a_i\leq 10^9\]
خروجی
در تنها سطر خروجی، باقی ماندهی «تعداد حالاتی که ۴ صندلی انتخاب شده بیقرپسند باشند» منهای «تعداد حالاتی که ۴ صندلی انتخاب شده باقرپسند باشند» به \(1\ 000\ 000\ 007\) را چاپ کنید.
مثال
ورودی نمونه ۱
6
2 2 1 2 1 2
خروجی نمونه ۱
1
ورودی نمونه ۲
9
2 2 1 2 1 3 2 2 2
خروجی نمونه ۲
1000000006
توضیح: در این مثال، اختلاف تعداد حالاتِ گفته شده برابر \(-1\) است که باقیماندهاش به \(1\ 000\ 000\ 007\) برابر با مقدار چاپ شده است.