Xóa theo đoạn giá trị

Cho một dãy gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$ và một số nguyên $x$. Đảm bảo rằng $1\le a_i\le x$ với mọi $i$.

Với mỗi cặp $(l,r)$, định nghĩa phép biến đổi $f(l,r)$ là: xóa khỏi dãy $a$ tất cả các phần tử có giá trị nằm trong đoạn $[l,r]$ (tức mọi $a_i$ thỏa $l\le a_i\le r$), rồi trả về dãy còn lại (giữ nguyên thứ tự các phần tử không bị xóa).

Ví dụ, nếu $a=[4,1,1,4,5,2,4,3]$ thì $f(2,4)=[1,1,5]$.

Hãy đếm số cặp $(l,r)$ thỏa $1\le l\le r\le x$ sao cho dãy $f(l,r)$ được sắp xếp không giảm. Lưu ý dãy rỗng cũng được coi là đã sắp xếp.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $x$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất: số cặp $(l,r)$ thỏa mãn.

Ràng buộc

• $1\le n,x\le {10}^6$
• $1\le a_i\le x$

Ví dụ