The bright red buildings and skies of the University of Fireloo.
The University of Fireloo is about to build a new on-campus residence named University of Fireloo Place (UFP), a village with 
~N~ apartment buildings!
Apparently, UFP's architects are quite superstitious, so they believe that the 
~K~ distinct numbers 
~u_1, \dots, u_K~ are "unlucky". As a result, for the 
~i^\text{th}~ apartment building, they want the floors to be numbered from 
~1~ to 
~f_i~ inclusive, but removing all floors with unlucky floor numbers.
Now, the architects need your help to determine how many floors each apartment in UFP should really have.
Constraints
~1 \le N \le 1\,000\,000~
~1 \le K \le 500\,000~
~1 \le f_i \le 1\,000\,000~ 
~(i = 1, \dots, N)~
~1 \le u_j \le 1\,000\,000~ 
~(j = 1, \dots, K)~
For 20% of the points, 
~N, f_i, u_j \le 100~, and 
~K \le 10~ for all 
~i~ and 
~j~.
For an additional 30% of the points, 
~N, f_i, u_j \le 100\,000~, and 
~K \le 10\,000~ for all ~i~ and ~j~.
Input Specification
The first line contains ~K~, the number of unlucky numbers the architects have considered.
The second line contains distinct, space-separated positive integers ~u_1, \dots, u_K~, the unlucky numbers.
The third line contains ~N~, the number of apartments to be built in UFP.
For the next ~N~ lines, the ~i^\text{th}~ line contains ~f_i~, the top floor number of the ~i^\text{th}~ apartment. It is guaranteed that no top floor number is an unlucky number.
Output Specification
Output ~N~ lines, where the ~i^\text{th}~ line contains one integer denoting the actual number of floors the ~i^\text{th}~ apartment should have.
Sample Input
2
4 13
2
16
14
Sample Output
14
12
Comments
Someone please tell me what I can do to make my code run faster :v
You need to change your approach to the question since your current time complexity is too large. You can read the editorial for a hint.