**Problem Link**

https://www.codechef.com/problems/COOLCHEF

**Prerequisites:**

binary search,permutation with repetition

There is no need to use square root decomposition like official editorial.I solved this problem(100) with binary search.Method in which even a beginner can understand

1.maintain a dictionary s with s[i] an array with indexes of elements in A which are equal to i.

Example A=[1,2,3,3,1] then s={1:[1,5],2:[2],3:[3,4]}

remove all the keys from s if length of s[key] is 1

2.maintain an array fact with c[i] =factorial(i)

eg fact=[1,2,6,24,120â€¦]

Start Iterating in the queries now

for l,r in queries: Let answer first be fact[r-l+1] iterate over keys in s: letind_1be number of elements in s[key] less then l.Find it using binary search letind_2be number of elements in s[key] less then or equal to r.Find using binary search again. set answer to answer/fact[ind_2-ind_1] print(answer)

done!!Wait not so fast you wonâ€™t get 100 with this

Now time for some Optimizations in the code.

When you iterate over keys in s add 2 conditions in the beginning.

if s[key][0]>r: continue if s[key][-1]<l: continue

As factorial can be huge number donâ€™t forget modulo arithmetic

**Done 100 points!!**

solution link:

https://www.codechef.com/viewsolution/24724216(only solution of python which got 100)

**Time Complexity:**

let complexity=0

for i in s:

complexity=complexity+log2(|s[i]|)

```
or
```

n complexity is ÎŁlog(|s[s.keys()[i]]|) i=1

so after summation complexity will be around log2(n) per query

Hope You liked the editorial!!!My first one.