All submissions for this problem are available.
Shah and Rukh survives and gets recruited by Hela. Now they have to work for Hela else she would throw them off into the hell. Since Hela is a God of Death, she wants more people to work for her. On the Earth, Hela finds people with either good deeds or bad deeds. Also there are some exceptional people with neither good nor bad deeds. She wants to select some good people who are honest and would be ready to work for her at any cost and at any time she calls.
So, Hela provides a set of deeds of N people to Shah and Rukh (1 based indexing). For optimum selection she asks Q queries. In each query she provides a range of people from l to r (both inclusive) and asks both of them to find minimum number of people from the given range such that the product of their deeds is maximum, as they would be more honest and dedicated people.
If Shah and Rukh makes Hela happy, they both would get combined and ultimately would become a legend named Shahrukh! Help Shah and Rukh find the minimum number of people with maximum product of their deeds.
- The first line of the input contains an integer N denoting the number of people .
- Next line contains N space separated integers denoting the deeds of ith person.
- Next line has the number of queries, Q, Hela would ask
- Following Q lines contain two space separated integers l and r denoting the range (both inclusive)
- 1 ≤ N ≤ 105
- -109 ≤ a[i] ≤ 109
- 1 ≤ Q ≤ 105
Print an integer on a new line for each query that denotes the answer.
7 6 8 9
Explanation : For the second query maximum product is 7 x 6 x 8, hence the ans is 3.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYP3|
Fetching successful submissions
If you are still having problems, see a sample solution here.