Candies - Candies
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 256 megabyte
Đăng bởi: chandoi

Nguồn: ACM-ICPC Vietnam Central Provincial Contest 

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.

Input

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)

Output

Each line contains the maximum total points for one tests.

Ví dụ

  • input
    1
    5
    3 2 4 9 1
    output
    31
Back to Top