P8898 [USACO22DEC] Feeding the Cows B

Farmer John 有 $N(1 \le N \le 10^5)$ 头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 $1 \cdots N$。 由于奶牛们都饿了，FJ 决定在 $1 \cdots N$ 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。 每头奶牛愿意移动至多 $K(0 \le K \le N-1)$ 个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。

无

无

### 样例 1 解释 注意对于某些子测试用例，存在多种可通过的方案使用最小数量的草地。例如，在第四个子测试用例中，以下是另一个可以通过的答案： $$\texttt{.GH..}$$ 这个方案在第二个位置种植一块喂饱更赛牛的草地以及在第三个位置种植一块喂饱荷斯坦牛的草地。这使用了最小数量的草地并确保了所有奶牛都在她们喜欢的草地的 $3$ 个位置以内。 ### 测试点性质 - 测试点 $2-4$ 满足 $N \le 10$。 - 测试点 $5-8$ 满足 $N \le 40$。 - 测试点 $9-12$ 满足 $N \le 10^5$。