L-R queries

Chef has an array A of size N. His friend Chuwi playing with this array in a next way: he chooses a continuous subarray A[L..R] and finds the maximum of (A[M] - A[L]) * (A[R] - A[M]) over all values of M where L ≤ M ≤ R. Chef wants to hopple Chuwi and changes elements of his array sometimes. Please help Chuwi to solve this easy problem. Input The first line of the input contains an integer T den