Question #1 : We will meet again
You are given an array A of N integers where A[i] represents the height of (i+1)th building.
If someone is in the ith building, he can move to the jth if and only if i < j and Ai < Aj.
Additionally, you are given an integer Q and two arrays U and V of size Q. This signifies that you are given Q queries. In the ith query Alice is on U[i]th building and Bobb is on V[i]th building. The answer to this query is minimum building number K that both Alice and Bobb can move to. If Alice and Bob cannot move to any common building then the answer to this query is -1.
Your task is to output an array Res where Res[i] is one answer of the ith query.
Input
First line of input is integer N
Subsequent N lines are A[i] where 0<=i<N
Followed by integer Q
Subsequent Q lines are U[i] where 0<=i<Q
Subsequent Q lines are V[i] where 0<=i<Q
Sample Cases
| Input | Output |
| 1 1 1 1 1 | [1] |
| 2 2 1 2 1 2 1 1 | [1,-1] |
| 3 1 3 2 3 1 3 2 2 1 3 | [2,3,-1] |
Question #2 : Mr Vega and 2 subsets
Given a set of N non-negative integers, Mr Vega wants to choose 2 non-empty, non-intersecting subsets. Additionally, Mr Vega also wants the difference of subset sums to be minimized.
Your task is to find the minimum possible difference of subset sums.
Note : There can be two or more equal integers in the set.
Input
First line of input is integer N
Subsequent N lines are A[i], where 0 <= i < N
Constraint
2 <= N
1 <= A[i] <= 10^9
Sample Cases
| Input | Output | Explanation |
| 4 39 44 9 57 | 4 | Subsets {39,9}{44} |
| 3 66 31 35 | 0 | Subsets {31,35}{65} |
| 4 97 12 19 90 | 0 | Subsets {97,12}{90,19} |
Question #3 : One large group
You have been given an array of size N called as AR. It is also given that you believe M is an unlucky number.
You want to select some numbers from array AR and put them into an another array called X. You can put any element from AR into the array X as long as the following condition is satisfied.
There should be no two numbers in the array X such that their sum is divisible by the number M.
Adding elements into the set X makes you happy. Hence, you have defined your Happiness Number to be the number of elements in the array X.
Your task is to find the maximum possible Happiness Number.
Input
First line of input is integer N
Second line of input is M
Subsequent lines are AR[i] where 0 <= i < N
Sample Cases
| Input | Output | Explanation |
| 3 2 1 2 3 | 2 | X[1,2] |
| 3 3 6 3 9 | 1 | X[3] |
| 3 3 6 4 1 | 3 | X[6,4,1] |