Задачи
Трое из Простоквашино
Трое из Простоквашино
\includegraphics{https://static.e-olymp.com/content/e7/e7e89769faab921727e63068b8c3f4224d8bb4d6.jpg}
- \textit{Дядя Федор, Дядя Федор, я научился строить дерево отрезков.}
- \textit{Подожди, Шарик, я занят.}
- \textit{Ну Дядя Федор, ну смотри какой я код написал:}
\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{Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из }\textbf{n }\textit{неотрицательных чисел и число }\textbf{k}, \textit{а ты мне скажешь сколько существует таких пар} \textbf{l}; \textbf{r }(\textbf{1 }≤ \textbf{l }≤ \textbf{r }≤ \textbf{n}), \textit{что функция, вызванная следующим образом}
\textbf{get_max(1, 1, n, l, r)}
\textit{вернет значение равное }\textbf{k}. \textit{Можно считать, что перед этим была вызвана функция}
\textbf{build(1, 1, n)}
- \textit{Хорошо, Дядя Федор!}
\InputFile
В первой строке находятся число \textbf{n }(\textbf{1 }≤ \textbf{n }≤ \textbf{10^6}) - количество элементов в массиве и \textbf{k }(\textbf{1 }≤ \textbf{k }≤ \textbf{10^9}) - значение, которое должна вернуть функция. В следующей строке находится \textbf{n }неотрицательных чисел, не превышающих \textbf{10^9} - элементы массива.
\OutputFile
Выведите единственное число -- ответ на задачу.
Входные данные #1
5 3 1 2 3 2 3
Выходные данные #1
11