NITT8 - Dating Rishi

no tags 

Dating Rishi

Its been Monday and Rishi Dude is 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 test cases.

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 test case.

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
BLANKRK: 2013-06-25 18:37:22

AC :D . . .
some WA due to silly mistak :P

Last edit: 2013-06-26 08:12:50
super human: 2013-06-13 22:19:14

enjoyed solving this one...!!!

:-): 2013-05-01 18:22:47

nice problem

Secret: 2012-12-26 14:49:56

@rishi u lucky man :P

Nurav: 2012-12-25 17:01:41

the value of height can be zero..cost me 1 WA

DINESH JANGID: 2012-12-15 13:59:41

@AGUS TRI WIBOWO @jack(chakradarraju)..I tried all and it got correct result within .02 sec but still SIGSEGV error....plz help.

I ran it under extreme conditions and still got correct ans under .01 sec. ID:8268661

Last edit: 2012-12-15 14:15:04
triveni: 2012-12-15 13:43:26

Enjoyed solving it in O(k*n)..:)Ac.. in 1st attempt...:)

007: Name stolen: 2012-12-01 04:49:56

nlogn is accepted....!!!!

Piyush Raman Srivastava: 2012-11-06 14:12:11

very nice question!! Njoyd solving it! :)

Lu Qi: 2012-11-02 05:10:46

I can't understand the problem desire.Can anyone explain this problem?


Added by:jack(chakradarraju)
Date:2012-09-30
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Radhakrishnan