הפרות המאוחדות של 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