+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- «مِسِریکس» از گرمایش جهانی به ستوه آمده و قصد دارد از خلاّقیّتش در زمینه‌ی بحران محیط زیست استفاده کند؛ امّا... حتما داستان هنرنمایی لیته و فیته بر روی صحنه را به یاد دارید. اکنون، مدّت زیادی از آن هنرنمایی می‌گذرد و لیته و فیته حسابی هنرمندان ماهری شده‌اند. مسریکس همراه با باقر و بی‌قر، دو نفر از دوستانش، برای تماشای هنرنمایی جدید لیته و فیته به سالن تئاتر رفته است. در همان لحظه فکری هوشمندانه به ذهن مسریکس می‌رسد و به باقر و بی‌قر می‌گوید هر کدام دو صندلی خالی از دو ردیف مختلف سالن تئاتر انتخاب کنند. به عبارت دیگر، باقر باید یک ردیف را انتخاب کند و سپس از آن ردیف دو صندلی خالی انتخاب کند. سپس بی‌قر باید یک ردیف دیگر را انتخاب کرده و دو صندلی خالی از آن ردیف انتخاب کند. در سالن تئاتر $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$ برابر با مقدار چاپ شده است.

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