The hackers of Hackerland want to deploy their applications on n servers. The ith server has requests[i] requests to serve but can serve a maximum of max req[i] requests only. In order to balance the load, the hackers need to redirect some requests of i ^ (th) server to some other servers. The latency induced in redirecting the request on the i ^ (th) server to the jth server is |i - j| where |x| represents the absolute value of x. The max_latency is defined as the maximum latency induced amongst all the redirections.

Given the arrays requests and max_req, find the minimum possible max_latency if the requests are redirected optimally such that no server has to serve more than the maximum requests it can serve. If there is no way to serve all the requests, report -1 as the answer.

Example:

Suppose n = 4 and requests = [1, 3, 2, 4] and max_req=[2, 1, 5, 3].

We can redirect 2 requests from the second server to the third server and 1 request from the fourth server to the third server. The maximum latency is equal to max( | 2-1|, | 3-2| ) = 1. It can be shown that this is the minimum possible max_latency possible.

Constraints

• 1≤n ≤ 10^5
• 1 ≤ requests[i] ≤ 10^9
• 1 ≤ max req[i] ≤ 10^9

int function(vector< int > requests, vector< int>max_req){  

}