在湖泊周围,有
共有
JOI 君携带了多张集章卡参加比赛。每张集章卡有左、右两个空格,可以加盖印章。每个空格最多加盖一枚印章。初始时,所有集章卡均为空白。
JOI 君参加集章拉力赛的流程如下:
- 首先,选择
个地点中的一个作为起点,并移动至该地点。若选择地点 ( ),则需要支付参与费用 。 - 接着,他可以指令主办方交换相邻的印章台。具体来说,可以交换道路
和 的印章台,或者交换道路 和 的印章台( )。每次交换需花费 ,JOI 君可以执行任意多次的交换(包括零次)。交换操作会在指令下达后立即执行。但为了防止作弊,不允许交换跨越 JOI 君所选起点的印章台。即:- 若起点为地点
,则禁止交换道路 和 的印章台。 - 若起点为地点
( ),则禁止交换道路 和 的印章台。
- 若起点为地点
- 此后,JOI 君从所选起点出发,按顺时针方向依次访问
个印章台。访问印章台时,他可以任意次地在该台为集章卡盖章。同一张卡可以在同一台同时加盖左、右两格。但每张集章卡必须先在左空格盖章,之后才能在右空格盖章,即若某卡的左空格未盖章,则不能在该卡的右空格盖章。
JOI 君想要收集尽可能多不同类型的已盖章卡。定义盖章卡
当且仅当
由于共有
有
可以证明,在给定的约束条件下,JOI 君总能通过足够大的成本收集到至少
编程回答 JOI 君的
输入格式
输出格式
输出
输入 #1
3 2 1 2 2 3 1 3 6 1 4 5 4 7 2 8 9
输出 #1
3 4
explanation
考虑 JOI 君选择地点
由于无法以
此外,若 JOI 君选择地点
该样例满足子任务
输入 #2
8 1 1 2 6 1 6 3 8 4 5 5 3 4 7 2 7 8 4 5 3 6 2 9 1 4 6 3 8 5 2 9 4 7 1 64
输出 #2
7
explanation
考虑 JOI 君选择地点
此时 JOI 君可获得
该样例满足子任务
输入 #3
9 4 4 3 5 3 8 1 5 8 1 7 6 2 4 9 6 9 2 7 12 9 4 8 7 1 20 5 8 7 4 13 5 9 10 3 7 8 6 39 81 73 79 64 52
输出 #3
1 18 3 10 1 1
explanation
该样例满足子任务
数据范围
。 。 是 的一个排列。 ( )。 。 ( )。- 所有输入值为整数。
子任务
: 。 : , , 。 : , 。 : 。 : 。 :无额外限制。