Armor Hall

Interview

Time limit2sMemory limit1024 MB

Summary

Given weighted points on a line, find the integer position that minimizes total weighted distance, taking the smallest coordinate on ties.

Level: Medium4 of 10
Topics: Prefix sum, Array, Greedy
Solved: No attempts yet

Problem

Tony Stark is setting up a new armor hall, a straight line with compartments for iron suits at some of its points. Tony wants to pick a point above which to build a takeoff hatch. The suits fly to Stark on their own, but he does not like waiting, so the hatch must be placed at an integer point where the total distance to all suits is the smallest. If several points tie, he wants the one with the smallest coordinate. Write a program for Jarvis that finds the optimal point for the hatch.

Input

The first line contains a single positive integer $n$ , the number of points with iron suit compartments ( $1 \le n \le 10^5$ ). The second line contains $n$ integers $a_i$ , the number of suits in the $i$ -th compartment ( $1 \le a_i \le 100$ ). The third line contains $n$ integers $x_i$ , the coordinate of the $i$ -th compartment ( $1 \le x_i \le 10^9$ ). More than one compartment can share a coordinate. It is guaranteed that $x_{i-1} \le x_i$ for every $i$ .

Output

Print one integer, the optimal point for placing the hatch.

Examples2

Example 1
Input
```
5
1 1 1 1 1
1 2 3 4 5
```
Expected output
```
3
```
Example 2
Input
```
4
1 4 1 1
1 2 3 3
```
Expected output
```
2
```