Зал брони

시간 제한2초메모리 제한1024 MB

요약

좌표 x_i에 가중치 a_i가 주어질 때 가중 거리 합을 최소로 하는 정수 좌표를 구하고, 동률이면 가장 작은 좌표를 출력한다.

난이도: 보통10점 중 4점
유형: 누적 합, 그리디, 수학, 정렬
정답자: 아직 제출이 없습니다

문제

Тони Старк обустраивает новый зал брони, который представляет из себя прямую, в некоторых точках которой находятся отсеки для железных костюмов.

Тони хочет выбрать точку, над которой нужно сделать люк для вылета. Костюмы самостоятельно прилетают к Старку, но он не любит ждать, поэтому люк должен быть расположен в такой целой точке, чтобы суммарное расстояние между ней и всеми костюмами было наименьшим. При этом если таких точек существует несколько, Старк хочет выбрать ту, в координата которой наименьшая.

Напишите программу для Джарвиса, которая сможет определить оптимальную точку для размещения люка.

입력

В первой строке задано одно натуральное число $n$ --- число точек, на которых находятся железные костюмы ( $1 \le n \le 10^5$ ).

Во второй строке содержатся $n$ целых чисел $a\_i$ --- количество костюмов в $i$ -м отсеке ( $1 \le a\_i \le 100$ ).

Во второй строке содержатся $n$ целых чисел $x\_i$ --- координата $i$ -го отсека ( $1 \le x\_i \le 10^9$ ). В одной координате может быть более одного отсека для костюмов. Гарантируется, что для любого $i$ выполняется $x\_{i -1} \le x\_i$ .

출력

Выведите одно целое число --- оптимальную точку для размещения люка.

예제2

예제 1
입력
```
5
1 1 1 1 1
1 2 3 4 5
```
예상 출력
```
3
```
예제 2
입력
```
4
1 4 1 1
1 2 3 3
```
예상 출력
```
2
```