轮班守夜

Zero核心外围有一道环形防线——不是墙，是一圈自动哨塔，每隔一段就有一个入口，但每个入口都必须有人值守。

"十二个入口。"你说，"但你们只有六个人。"

"轮班。"CC说，"一人看两个门，换着来。"

"不对。"Echo说，"哨塔的值守有规则——相邻的两个入口不能同时空岗，但一个人不能连续值守超过四个小时，不然会累垮。"

"那就排班。"你说，"把每个人分配到具体的时间段和入口。"

"咋个排？"CC问，"人这么少，门这么多。"

"用图。"你说，"把入口看成点，相邻的入口连成边。每个点需要被覆盖，每条边不能两边同时空。"

你开始画。十二个入口排成一个圈，每个入口是一个点，相邻点之间连边。六个人，每个人负责一个时间段，覆盖尽可能多的入口。

"这样排。"你说，"老周守0-4点，看东1、东2。陈叔守4-8点，看东3、东4。小马守8-12点，看南1、南2。"

"那我们呢？"CC问。

"我们三个守最忙的时段。"你说，"12-16点，16-20点，20-24点。每人看两个入口，但不连续——中间隔一个休息。"

"为啥子不连续？"

"因为连续值守会累。"你说，"隔一个，喘口气。"

CC看着那张排班表——密密麻麻的字，但每一行都清清楚楚。

"你以前排过班？"

"没有。"你说，"但我会算。"

"算？"

"对。"你说，"这就是一道题——用最少的班次，覆盖所有的入口，满足所有规则。"

Echo把排班表投影到墙上——蓝色的光，像一张星图。

"第一班。"她说，"老周，0点。"

"收到。"老周的声音从通讯器里传来，有点哑，但很清楚。

题目描述

环形防线有 $n$ 个入口。每个入口需要被值守。一个人可以值守多个入口，但不能值守相邻的入口（会累垮）。求最少需要多少人才能覆盖所有入口。

输入格式

$n$。然后 $n$ 个整数，表示每个入口的值守难度（权重）。

输出格式

最少人数。

输入样例

3 2
1 2
2 3

输出样例

No Solution
No Solution
No Solution

提示

• 环形结构，相邻不能同时选。
• 用图论建模：每个入口是一个点，相邻入口连边。
• 求最大独立集——选最多的不相邻入口，然后用总人数减去独立集大小。

"排好了。"你说。

"六个人。"CC数了数，"刚好够。"

"刚好够。"Echo说，"不多不少。"

"那如果不够呢？"你问，"如果只有五个人？"

"那就有人要守三个门。"CC说，"累一点，但能撑。"

"如果只有四个人？"

"那就得有人不睡了。"CC说，"轮流眯一会儿。"

"如果只有三个人？"

CC看着你，眼神很认真。

"那就死撑。"她说，"撑到有人来。"

"如果没人来呢？"

"那就死。"CC说，"但死之前，门不能空。"

Echo的指示灯闪了一下。

"有人来了。"她说。

"谁？"

"平民。"Echo说，"最后一批。他们要从东门出去。"

"走。"你说，"去引路。"

[第二题：引路归家]