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

---

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

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

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