Chú ý: bộ test do mình make(có thể có lỗi), không phải bộ test chính thức của kì thi
Thinh loves candy very much and he is playing a game with candies. He has N candies numbered 1 to N from left to right. The i-th candy has a value A[i]. He wants to eat these candies one by one such that he can maximize the total points after eating all of them. The total points of eating candies are calculated as follows:
• Whenever Thinh eats one candy, this candy will disappear and he will get an amount of points equal to the product of the value of it and the smaller value between 2 nearest candies to the left and right of it.
• If there is no candy on the left or on the right, its value is assumed to be 1.
Let's help Thinh find the optimal way to eat these candies.
One line contains T, which is number of tests (T ≤ 50). Each test contains 2 lines:
• The first line contains a integer N (N ≤ 50)
• The second line contains N numbers which is the values of candies from left to right. (1 ≤ V[i] ≤ 1000)
Each line contains the maximum total points for one tests.