There are N towers arranged in a single line. You want to rearrange all the towers.

Given an array H of size N, where Hi denotes the height of tower i. You can rearrange this array in whatever way you like.

Beauty is defined as follows:

If j is the position of the tower i in the final arrangement, you add Hi*abs(i-j) to the Beauty.

Your task is to find the maximum Beauty you can achieve, after rearranging the towers.

I could only come with bitmask dp solution but here N is 10^3 so it won't work.