ترسل أبقار Farmer John المتحدة (UCFJ) وفدًا إلى International bOvine olympIad (IOI).

تشارك $N$ بقرة في اختيار الوفد ($1 \leq N \leq 2 \cdot 10^5$). تقف في صف، وسلالة البقرة $i$ هي $b_i$.

يتكون الوفد من فترة متجاورة تضم بقرتين على الأقل: الأبقار $l\ldots r$ لعددين صحيحين $l$ و$r$ يحققان $1\le l<r\le N$. تُعين البقرتان على طرفي الفترة « قائدتين ». لتجنب النزاع داخل السلالة، يجب أن تختلف سلالة كل قائدة عن سلالة كل فرد آخر في الوفد، سواء كان قائدة أم لا.

ساعد UCFJ، لأسباب ضريبية، في تحديد عدد طرق اختيار وفد إلى IOI.

الإدخال

يحتوي السطر الأول على $N$.

يحتوي السطر الثاني على $N$ عددًا صحيحًا $b_1,b_2,\ldots,b_N$، كل منها ضمن المجال $[1,N]$.

الإخراج

عدد الوفود الممكنة في سطر واحد.

قد تتطلب الأعداد الكبيرة أنواع أعداد صحيحة من 64 بت (مثل long long في C/C++).

أمثلة

الإدخال 1

7
1 2 3 4 3 2 5

الإخراج 1

13

ملاحظة

يقابل كل وفد أحد أزواج القائدتين التالية:

$$(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).$$

المهام الفرعية

• تحقق حالات الاختبار 1–3 الشرط $N\le 100$.
• تحقق حالات الاختبار 4–8 الشرط $N\le 5000$.
• لا توجد قيود إضافية لحالات الاختبار 9–20.

نسبة المسألة: Benjamin Qi