好⽃的⽜

题目描述

你有 个⽜棚，从左到右⼀字排开。你希望把 头⽜安置到⽜棚⾥。⿇烦的是，你的⽜很好⽃，如果他们附近有 其他的⽜，他们就会不安分地去挑事。其中，第 头⽜的攻击范围是 ，这意味着，如果他的左边 个⽜棚或 右边 个⽜棚⾥有其他⽜，他就会去挑事。 你想留下连续的⼀段⽜棚，并把其他⽜棚都卖掉。请问你最少需要留下多少⽜棚，才能保证⾄少存在⼀种⽅案能够 把所有的 头⽜都安置进剩余的⽜棚⾥，且没有⽜会挑事？

输入格式

第⼀⾏ 1 个正整数 。 接下来⼀⾏ 个⽤空格隔开的正整数 。 接下来⼀⾏ 个⽤空格隔开的正整数 。

输出格式

输出⼀⾏⼀个整数，表⽰你最少需要留下多少⽜棚。 3.2.4 特别提醒 在常规程序中，输⼊、输出时提供提⽰是好习惯。但在本场考试中，由于系统限定，请不要在输⼊、输出中附带任 何提⽰信息。

样例输入 #1

2
1 2
1 2

样例输出 #1

1 4
3.2.7 样例解释 1
你可以留下 个⽜棚，并如此安排你的⽜：
牛棚 牛棚 牛棚 牛棚
⽜ ⽜

样例输入 #2

3
1 2 3
3 2 1

样例输出 #2

1 7
3.2.10 数据规模
对于 的测试点，保证 ；
对于另外 的测试点，保证 ；
对于 的测试点，保证 ；
对于所有测试点，保证 ， 。

数据范围

见题目描述

知识点与难度

本题涉及的知识点从属于 GESP 6级，难度等级：⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。