Given *N* arrays of arbitrary length each, and *M* queries in form : *a* *b*. For each query output the number of arrays such that there exist *Array*[*i*] = *a* *Array*[*j*] = *b* and *i* < *j* (Basically, number of arrays such that *a* comes before *b*). Also, there can be any number of a's or b's in any array

*N*, *M*, *a*, *b* < = 10^{5} Consider that length of all arrays is < = 10^{5}

Example: Arrays

1 2 3 4

2 4

2 3 1 4

and queries are (1, 3) , (2, 4) , (1, 4) , (4, 1) answers are 1 , 3 , 2 , 0

Constraints?

Updated

Let

maxN= 10^{5}.1) Number of array which exist that pair for a,b that is number of array such there first occurrence of element a more to the left than last occurrence of element b.

2) Before requests you can precalculate number of arrays, which length is smaller than and they satisfy the condition for each pair (a,b) in

map<pair<int,int> ,int> . The size of this map will not be greater than .3) Also you want to precalc for all posible value and array first and last occurrence of it.

For each request you will get appropriate value in map and consider all arrays with size not smaller than (count of this arrays not bigger than ). Using 1 and 3 its easy to consider them.

Сomplexity .

Using Hash Tables complexity will be .

I missed the part with arrays of smaller length, really stupid of me... Not hard problem at all. Thank you

For each array with size smaller than we will use naive algo: brute positions

i<jand if pair (Array[i],Array[j]) we don't see in this array before will update info in map likem[{Array[i],Array[j]}]++.Oh, I meant when I was solving problem, thank you anyway