Sum of products (hard version)

Given an array $arr_1,arr_2...arr_n$ consisting of $n$ integers. We define the $SOP$ value of some subarray $arr[l...r]$ as the sum of all $arr_i\cdot arr_j\cdot arr_k$ where $l\leq i$ < $j$ < $k\leq r$. You have to answer $q$ queries, in each query you will be given two integers $l$ and $r$ and you have to find the $SOP$ value of the subarray $arr[l...r]$. As the answer can be very large, print a