• محدودیت زمان: ۰.۵ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

روزی دانش‌پژوهی از دانش‌پژوهان المپیاد کامپیوتر، در حرکتی اعتراضی به طرّاحی از طرّاحان خفن سوالات می‌گوید: «هیچکدومتون سوال طرح نمی‌کنید، همش می‌رید از یه جای ناشناخته سوال برمی‌دارید، می‌دید!»

طراح خفن در لحظه سوال زیر را طرح کرده و به دانش‌پژوه می‌دهد تا حقّانیّت خود را ثابت کند.

آرایه‌ای به نام $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