NITT8  Dating Rishi
Dating Rishi
Its been Monday and Rishi Dudeis planning to select a girl to date for this week. So all N girls are standing in a line from 1 to N so that Rishi will select one of them. The girls are standing in a straight line but randomly. They know they cannot predict what Rishi The Great likes, He may like hot, smart, tall, short, witty, white, black or anything. But wait, Rishi, the Coolest Dude plans to date two girls this week !!! How lucky they are ????. But he wants to select two girls whose friendship quotient is maximum so that they wont fight too much over Rishi during the date. He is shy too !. Friendship quotient is defined as the product of absolute difference between the position of the two girls and the minimum height of the two girls.
Can you help Rishi to find the maximum friendship quotient ?
Input Specification
The first line of input file contains T which denotes number of testcases.
2*T lines follows.
First line of each test case contains an integer N.
Second line of each test case contains N space separated integers denoting the height of each girl.
Output Specification
The output must contain T lines each line corresponding to a testcase.
Constraints
T <= 20
N <= 100000
Height[i] <= 10^9
Sample Input:
2 4 3 2 1 3 5 4 2 3 1 4
Sample Output:
9 16
hide comments
deerishi:
20161016 07:21:22
From a guy who goes by the name Rishi , its an awesome problem! lol!! 

ashish22_dwd:
20150708 19:37:31
nice problem.. solved in O(n) time. AC in 0.02s Last edit: 20161018 22:18:25 

Akshat Mathur:
20150617 14:43:59
Really nice problem.....learnt a lot !! 

sobriquet:
20140920 12:59:30
Awesome problem. Mind long long instead int. 

N0VICE:
20140823 17:16:33
150th AC :)


AKASH GOEL:
20140823 14:24:32
gud one


AAKASH TYAGI:
20140809 22:08:21
a very good problem


Archit Jain:
20140809 16:08:02
finally ac after a long time


TAUSHIF ALI:
20140714 21:48:20
nic one :) 

Agam Gupta:
20140530 12:46:21
gud one !! 
Added by:  jack(chakradarraju) 
Date:  20120930 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Radhakrishnan 