Three from Creamville

- Uncle Peter, Uncle Peter, I learned to build the segment tree.

- Wait, Spot. I'm busy.

- Well, Uncle Peter, 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, Spot, if you've dealt with this topic so well, let me give you an array of $N$ non-negative integers and number $k$, and you will tell me how many such pairs there are $l$; $r$ (1 \le l \le r \le N), that the function called as follows

get_max(1, 1, N, l, r)

returns a value of $k$. We can assume that the function was called before this

build(1, 1, N)

- Ok, Uncle Peter!