\includegraphics{https://static.e-olymp.com/content/e7/e7e89769faab921727e63068b8c3f4224d8bb4d6.jpg} - \textit{Uncle Fedor, Uncle Fedor, I learned to build the segment tree.} - \textit{Wait, Sharik. I'm busy.} - \textit{Well, Uncle Fedor, look at my code:} \textbf{int} build(\textbf{int} v, \textbf{int} left, \textbf{int} right) \{ \textbf{if (left == right) \{} \textbf{t\[v\] = a\[left\];} \textbf{return 0;} \textbf{\}} \textbf{int mid = (left+right) / 2;} \textbf{build(v*2, left, mid);} \textbf{build(v*2+1, mid+1, right);} \textbf{t\[v\] = max(t\[v*2\], t\[v*2+1\]);} \textbf{return 0;} \textbf{\}} \textbf{int get_max(int v, int left, int right, int lpos, int rpos) \{} \textbf{if (left == lpos && right == rpos)} \textbf{return t\[v\];} \textbf{if (lpos > rpos)} \textbf{return -1;} \textbf{int mid = (left+right) / 2;} \textbf{return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),} \textbf{get_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));} \textbf{\}} - \textit{Well, Sharik, if you're so good to deal with this topic, let me give you an array of }\textbf{n }\textit{non-negative integers and number }\textit{\textbf{k}}\textit{, and you will tell me how many there are such pairs }\textit{\textbf{l}}\textit{; }\textit{\textbf{r }}\textit{(}\textit{\textbf{1 }}\textit{≤ }\textit{\textbf{l }}\textit{≤ }\textit{\textbf{r }}\textit{≤ }\textit{\textbf{n}}\textit{), that the function called as follows} \textbf{get_max(1, 1, n, l, r)} \textit{returns a value of }\textbf{k}. \textit{We can assume that before was called the function} \textbf{build(1, 1, n)} - \textit{Ok, Uncle Fedor!} \InputFile The first line contains the number \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{10^6}) of elements in the array and \textbf{k }(\textbf{1 }≤ \textbf{k }≤ \textbf{10^9}) - the value that the function should return. The next line contains \textbf{n }non-negative integers not exceeding \textbf{10^9} - the array elements. \OutputFile Print one number -- the answer to the problem.