题目描述
八千代有一个长度为 n 的整数序列 S,序列的每个位置(下标从 1 开始)都有一个权值 ai。
她可以将这个序列连同权值一起复制并首尾拼接若干次。具体来说,若他选择拼接使得总份数为 m(m≥1),则会得到一个长度为 m×n 的新序列 S′ 和对应的新权值序列 a′。对于任意的 0≤c<m 和 1≤i≤n,满足 Scn+i′=Si 且 acn+i′=ai。
八千代现在想对得到的新序列 S′ 进行若干次(可以为 0 次)消除操作。每次操作的规则如下:
- 选定两个下标 i,j 满足 1≤i<j≤∣S′∣,且 Si′=Sj′。
- 将 S′ 和 a′ 中的第 (i+1) 个到第 j 个元素删去。
- 操作完成后,序列剩余的元素会按照原顺序重新紧凑排列,序列的总长度相应减少。
八千代想知道,在经过恰当份数的拼接和任意次消除操作后,整个剩余序列的权值和最小是多少?以及在保证权值和最小的前提下,最少需要多少份原序列拼接(即求最小的 m)?
输入格式
输入包含三行。
第一行包含一个整数 n(1≤n≤3×105),表示初始序列 S 的长度。
第二行包含 n 个整数 S1,S2,⋯,Sn(1≤Si≤3×105),表示初始序列 S 的元素。
第三行包含 n 个整数 a1,a2,⋯,an(1≤ai≤3×105),表示每个位置对应的权值。
输出格式
输出一行包含两个整数,用空格隔开:
- 第一个整数表示经过操作后,剩余序列的最小权值和。
- 第二个整数表示为了达到该最小权值和,最少需要的原序列总份数。
6
1 1 4 5 1 4
1 9 1 9 8 10
2 1
提示
在本样例中,最优策略是仅使用 1 份原序列(即 m=1,不进行额外复制)。
初始序列 S′ 为 [1,1,4,5,1,4],对应的权值 a′ 为 [1,9,1,9,8,10]。
八千代可以进行以下两次操作:
- 选择 i=1,j=2(此时 S1′=S2′=1),删去第 i+1∼j 个元素(即删去第 2 个元素)。操作后序列 S′ 变为 [1,4,5,1,4],权值 a′ 变为 [1,1,9,8,10]。
- 在新序列中选择 i=2,j=5(此时 S2′=S5′=4),删去第 i+1∼j 个元素(即删去第 3,4,5 个元素)。操作后序列 S′ 剩余 [1,4],权值 a′ 剩余 [1,1]。
此时无法继续消除,剩余序列的权值和为 1+1=2。可以证明在任何拼接份数和操作下,权值和不可能小于 2。