KOSPC13B - Determine the vismin value !

no tags 

               There are N students in a class. The teacher wants to test the acuity of the students' vision as well as mind in an entertaining way.She comes up with an idea.
                The students were made to stand in a line and numbered from 1 to N, each carrying a board with a number K on it.The test is as follows : the teacher calls out a student X;the student can look at either sides and choose a student Y who carries a board with a number greater than or equal to the number on the board carried by X and calculates a value called as "vismin value". "vismin value" is defined as the product of the difference between the positions of X and Y and the smallest of the numbers on the boards carried by X and Y.If it is not possible to choose Y,"vismin value" will be 0. Now, the way the students are tested is how far the students maximise the "vismin value".For each student called, he/she answers with a "vismin value".If it is maximum, teacher says "Maximum".If there is a greater value possible, the teacher says the value which the student is running short of, to attain the maximum value.If the value said by the student is greater than the maximum value possible, the teacher says "Not possible".
Consider yourself as the teacher and print the output accordingly.

Input:

The first line of the input consists of N,the number of students in the class.
The second line consists of N space separated integers K representing the numbers on the boards carried by the respective students.
Then, each line/query consists of a student number separated by the vismin value determined by the student.
Input ends with both student number and vismin value equal to 0.

Output:
For each query, print what the teacher would have said.

Constraints :

1<=N<=100000
1<=k<=10^9

Number of queries <= 10000


Input :
5
5 3 6 7 1
1 13
1 18
1 15
4 5
5 4
0 0
Output :
2
Not possible
Maximum
Not possible
Maximum


hide comments
Kousik Kumar: 2013-06-28 17:28:48

Is there an O(n) algorithm? O(n + q * log(n)) TLE's :(

Last edit: 2013-06-28 17:29:24
Branfili: 2013-03-17 05:57:33

Now that the cluster is pyramid can you loosen up the time limit a bit?

(Tjandra Satria Gunawan)(曾毅昆): 2013-02-06 08:00:09

Please change the cluster to pyramid... I want to know my program running time accurately..


Added by:Pandian
Date:2013-01-26
Time limit:0.146s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem