Follow zaozijie Meow, follow zaozijie Thank you Meow.
Given a sequence of integers a1,…,ana_1,\dots,a_na1,…,an , you need to answer mmm questions.
The answer to a
question l,rl,rl,r is the amount of
(i,j,k)(i,j,k)(i,j,k) s.t.
l≤i<j<k≤r,ai=ak>ajl\le i<j<k\le r,\;a_i=a_k>a_jl≤i<j<k≤r,ai=ak>aj .
1≤ai≤n
1≤l≤r≤n1\le l\le r\le n1≤l≤r≤n
1≤n,m≤5×1051\le n,m\le 5\times 10^51≤n,m≤5×105