• محدودیت زمان: ۴ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• منبع: آزمون نهایی سوم دوره ۲۷ المپیاد کامپیوتر

---

«تو مرد این کارا نیستی»، این واکنش امین بود وقتی علی داستان پروژه‌ی یک ملیاردی را برایش تعریف کرد.

امین به او گفت برای انجام این پروژه می‌بایست نظریه‌ اعدادش خیلی قوی باشد، برای سنجش سطح نظریه‌ی اعداد او، امین دنباله‌ی \(a_0, a_1, \dots, a_{n-1}\) به طول \(n\) را به او داد و از او خواست تعداد سه‌تایی‌های مرتب \((i,j,k)\) که \(0 \le i < j < k < n\) و \(gcd(a_i, a_k) = a_j\) را بیابد.

علی به آن پول خیلی احتیاج دارید، کمکش کنید تا این مسئله را حل کند تا کمک امین را برای پروژه داشته باشد.

ورودی

در سطر اول ورودی عدد \(n\) آمده‌است.

در سطر بعد \(n\) عدد \(a_0, a_1, \dots, a_{n-1}\) آمده‌است. \[3 \le n \le 100\ 000\] \[1 \le a_i \le 100\ 000\]

خروجی

در تنها سطر خروجی تعداد سه‌تایی‌های خواسته‌شده را چاپ کنید.

زیرمسئله‌ها

زیرمسئله	نمره	محدودیت
۱	۶	\(n \le 200\)
۲	۱۳	\(n \le 2000\)
۳	۳۱	\(a_i \le 10\)
۴	۵۰	بدون محدودیت اضافی

مثال

ورودی نمونه ۱

5
6 2 3 4 3

خروجی نمونه ۱

2

ورودی نمونه ۲

5
1 1 1 1 1

خروجی نمونه ۲

10

ورودی نمونه ۳

8
1 2 3 4 1 2 3 4

خروجی نمونه ۳

8