+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- روزی دانش‌پژوهی از دانش‌پژوهان المپیاد کامپیوتر، در حرکتی اعتراضی به طرّاحی از طرّاحان خفن سوالات می‌گوید: «هیچکدومتون سوال طرح نمی‌کنید، همش می‌رید از یه جای ناشناخته سوال برمی‌دارید، می‌دید!» طراح خفن در لحظه سوال زیر را طرح کرده و به دانش‌پژوه می‌دهد تا حقّانیّت خود را ثابت کند. آرایه‌ای به نام $a$ به طول $n$ داریم، تعداد سه تایی‌های $1 < x < y < z < n$ را می‌خواهیم به طوری که $a_{z} < a_{x} < a_{y}$ باشد. دانش‌پژوه که از کرده‌ی خود پشیمان است از شما کمک می‌خواهد تا این مقدار را بدست آورید. # ورودی در سطر اول ورودی عدد $n$ آمده‌است. در سطر بعدی $n$ عدد آمده است که عدد $i$ام برابر با $a_{i}$ است. $$1 \le n \le 300\ 000$$ $$1 \le a_{i} \le 10^{9}$$ # خروجی در تنها سطر خروجی، مقدار گفته شده در صورت سوال را چاپ کنید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۱۰ | $n \le 500$| | ۲ | ۱۵ | $n \le 2\ 000$ | | ۲ | ۲۰ | $a_i \le 100$ | | ۴ | ۵۵ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 3 2 3 1 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 7 1 3 3 4 4 2 2 ``` ## خروجی نمونه ۲ ``` 8 ```