题目描述

小红喜欢玫瑰和牡丹，小红在他的花坛中种了 $n$ 盆花，每盆花要么是玫瑰，要么是牡丹，并按顺序从左往右依次编号，从 1 到 $n$。花坛的观赏度定义为玫瑰与牡丹的盆数之差的绝对值。现在定义一种操作：选取一个连续的区间 $[1, r]$，将编号从 1 到编号 $r$ 的花盆中的玫瑰替换成牡丹，将牡丹替换成玫瑰。

小红不关心观赏度的高低，而是关心经过至多一次这样的操作，花坛可能出现的观赏度的种类数。请问经过至多一次这样的操作，小红的花坛一共有多少种不同的观赏度？

定义数组 $s$ 表示花的种类。其中，玫瑰和牡丹分别表示为 $-1$ 和 $1$，则 $\lvert \sum\limits^{n}_{i=1} s_i \rvert$ 即为花坛的观赏度。

不难发现，对于区间 $[l,r]$ 进行一次操作，区间贡献会变成其和的相反数，等价于 $s$ 的总和减去两倍区间 $[l,r]$ 的和。 所以我们分别计算 $s$ 中子序列的最大值和最小值，以两值为边界枚举一遍，中间用 set 统计答案即可。

Python

from collections import defaultdict

n = int(input())