e-olymp
Задачи

Трое из Простоквашино

Трое из Простоквашино

prb4491 - Дядя Федор, Дядя Федор, я научился строить дерево отрезков.

- Подожди, Шарик, я занят.

- Ну Дядя Федор, ну смотри какой я код написал:

int build(int v, int left, int right) {

if (left == right) {

t[v] = a[left];

return 0;

}

int mid = (left+right) / 2;

build(v*2, left, mid);

build(v*2+1, mid+1, right);

t[v] = max(t[v*2], t[v*2+1]);

return 0;

}


int get_max(int v, int left, int right, int lpos, int rpos) {

if (left == lpos && right == rpos)

return t[v];

if (lpos > rpos)

return -1;

int mid = (left+right) / 2;

return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),

get_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));

}

- Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из n неотрицательных чисел и число k, а ты мне скажешь сколько существует таких парl; r (1 l r n), что функция, вызванная следующим образом

get_max(1, 1, n, l, r)

вернет значение равное k. Можно считать, что перед этим была вызвана функция

build(1, 1, n)

- Хорошо, Дядя Федор!

Входные данные

В первой строке находятся число n (1 n 106) - количество элементов в массиве и k (1 k 109) - значение, которое должна вернуть функция. В следующей строке находится n неотрицательных чисел, не превышающих 109 - элементы массива.

Выходные данные

Выведите единственное число – ответ на задачу.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
5 3
1 2 3 2 3
Выходные данные #1
11
Автор Александр Бурков
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года