排列（arrange）

题目描述

$\text{Alpha}$ 终于和 $\text{Beta}$ 见面了，并说服了 $\text{Beta}$ 来学OI和帮 $\text{Alpha}$ 出题。

$\text{Alpha}$ 和 $\text{Beta}$ 各出 $n$ 题，$\text{Alpha}$ 每题的类型为 $p_1,\cdots ,p_n$ 且互不相同，难度为 $a_1,\cdots, a_n$， $\text{Beta}$ 每题的类型为 $q_1,\cdots,q_n$ 且互不相同，难度为 $b_1,\cdots,b_n$。他们希望出一场毒瘤的模拟赛，$\text{Alpha}$ 会挑选他的题中的一个区间 $[l_1,r_1]$ 的题作为比赛题目， $\text{Beta}$ 同样也会挑选一个区间 $[l_2,r_2]$。

他们希望这场比赛每道题的类型都不同且难度和最大，你需要求出这个最大难度。为了让他们知道该选哪些题，你需要输出 $l_1,r_1,l_2,r_2$。

输入格式

第一行一个数 $n$，接下来的 $4$ 行，分别表示 $\text{Alpha}$ 题的类型 $\{p\}$，$\text{Alpha}$ 题的难度 $\{a\}$，$\text{Beta}$ 题的类型 $\{q\}$，$\text{Beta}$ 题的难度 $\{b\}$。

输出格式

第一行一个整数表示最大难度和。

样例1

输入样例

10
1 13 7 12 16 14 2 4 18 9 
863188151 578895948 745326321 879803922 33340187 773018775 1611961 328481539 836778643 42132740 
15 12 9 10 13 6 7 16 5 14 
490111184 44160605 178712634 153844762 469335595 59339337 678804831 156639755 813410172 285569928 

输出样例

5895988359

样例2

见下发样例

数据范围

• 子任务1(10分)： $n ≤500$。

• 子任务2(20分)：$n ≤5000$，依赖测试包1。

• 子任务3(10分)： $p_i,q_i$ 为 $1...n$ 的排列且随机，$a_i,b_i$ 在范围内随机。

• 子任务4(30分)：$n ≤10^5$，依赖测试包2。

• 子任务5(30 分)：$n ≤10^6$，依赖测试包4。

对于所有数据，保证 $1≤p_i,q_i ≤2 \times n，n ≤10^6,1 ≤ai,bi≤ 10^9$。