Three from Prostokvashino
- Uncle Fedor, Uncle Fedor, I learned to build the segment tree.
- Wait, Sharik. I'm busy.
- Well, Uncle Fedor, look at my code:
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));
}
- Well, Sharik, if you're so good to deal with this topic, let me give you an array of n non-negative integers and number k, and you will tell me how many there are such pairs l; r (1 ≤ l ≤ r ≤ n), that the function called as follows
get_max(1, 1, n, l, r)
returns a value of k. We can assume that before was called the function
build(1, 1, n)
- Ok, Uncle Fedor!
Input
The first line contains the number n (1 ≤ n ≤ 10^6) of elements in the array and k (1 ≤ k ≤ 10^9) - the value that the function should return. The next line contains n non-negative integers not exceeding 10^9 - the array elements.
Output
Print one number – the answer to the problem.