لنعرّف $\operatorname{mex}(S)$ على أنه أصغر عدد صحيح غير سالب غير موجود في المجموعة $S$.
تُعطى تبديلاً $p$ يتكون من $n$ عنصراً من $0$ إلى $n - 1$. ولديك أيضاً $m$ قطعة $[l_i, r_i]$ تستخدمها لبناء بيان (رسم بياني) بالطريقة التالية:
- لكل زوج من الرؤوس $i \neq j$، تضيف ضلعاً تساوي تكلفته قيمة $\operatorname{mex}$ لاتحاد قيم التبديل على القطعتين $[l_i, r_i]$ و $[l_j, r_j]$. وبشكل أكثر رسمية، تساوي التكلفة $\operatorname{mex}(\{p_k \mid k \in [l_i, r_i] \cup [l_j, r_j]\})$.
أوجد الشجرة الممتدة الصغرى للبيان الموصوف.
الإدخال
يحتوي السطر الأول على عددين صحيحين ($2$ أعداد) هما $n, m$ ($2 \le n, m \le 3 \cdot 10^5$) — طول التبديل وعدد القطع.
يحتوي السطر الثاني على $n$ عدداً صحيحاً $p_i$ ($0 \le p_i \le n - 1$) — وصف التبديل $p$.
تحتوي الأسطر الـ $m$ التالية على أزواج من الأعداد الصحيحة $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — وصف القطع.
الإخراج
في سطر واحد، اطبع إجابة المسألة.
أمثلة
الإدخال 1
6 4 3 1 5 2 0 4 3 6 1 2 2 5 4 6
الإخراج 1
8
الإدخال 2
2 2 0 1 1 2 1 2
الإخراج 2
2