B. Coupons and Discounts

编程竞赛赛季已经开启，是时候为 ICPC 进行训练了。Sereja 已经教练他的队伍多年，他知道仅准备题目和题解不足以准备好训练课程。由于训练课程持续数小时，队伍会感到饥饿。因此，Sereja 订购了一些披萨，以便比赛结束后立即食用。 队伍计划在 #cf_span[n] 个连续天内进行 #cf_span[n] 次训练。在每次训练日，Sereja 为当天出席的每个队伍订购恰好一个披萨。他已知第 #cf_span[i] 天将有 #cf_span[ai] 个队伍出席。 Sereja 最喜欢的比萨店提供两种折扣：第一种折扣是当某天购买两个披萨时生效；第二种是优惠券，允许在两个 *连续* 天内购买一个披萨（总计两个披萨）。 由于 Sereja 在这家店订购了大量披萨，他是黄金客户，可以在任何一天无限制地使用任意数量的折扣和优惠券。 Sereja 希望在第 #cf_span[i] 天恰好订购 #cf_span[ai] 个披萨，且仅使用折扣和优惠券。注意，他绝不会购买超过当天所需数量的披萨。请帮助他确定，是否可以在仅使用优惠券和折扣的情况下，每天购买所需数量的披萨。注意，结束第 #cf_span[n] 天后，不允许有任何未使用的优惠券处于激活状态。 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000]) —— 训练会话的次数。 第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[0 ≤ ai ≤ 10 000]) —— 每天出席的队伍数量。 如果存在一种仅使用优惠券和折扣、且不于任何一天多买披萨的订购方案，则在输出的唯一一行中打印 "_YES_"（不含引号）；否则，打印 "_NO_"（不含引号）。 在第一个样例中，Sereja 可以使用一张优惠券在第一天和第二天各买一个披萨，一张优惠券在第二天和第三天各买一个披萨，再使用一个折扣在第四天买两个披萨。这是该样例中订购披萨的唯一方式。 在第二个样例中，Sereja 无法在不额外购买披萨的情况下使用任何优惠券或折扣。注意，某些天可能没有队伍参加训练。 ## Input 输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 200 000]) —— 训练会话的次数。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[0 ≤ ai ≤ 10 000]) —— 每天出席的队伍数量。 ## Output 如果存在一种仅使用优惠券和折扣、且不于任何一天多买披萨的订购方案，则在输出的唯一一行中打印 "_YES_"（不含引号）；否则，打印 "_NO_"（不含引号）。 [samples] ## Note 在第一个样例中，Sereja 可以使用一张优惠券在第一天和第二天各买一个披萨，一张优惠券在第二天和第三天各买一个披萨，再使用一个折扣在第四天买两个披萨。这是该样例中订购披萨的唯一方式。在第二个样例中，Sereja 无法在不额外购买披萨的情况下使用任何优惠券或折扣。注意，某些天可能没有队伍参加训练。

Let $ a_1, a_2, \dots, a_n $ be non-negative integers representing the number of pizzas needed on day $ i $. We are allowed to use two types of operations: - **Discount**: On a single day $ i $, cover two pizzas (i.e., reduce $ a_i $ by 2). - **Coupon**: Over two consecutive days $ i $ and $ i+1 $, cover one pizza on each (i.e., reduce $ a_i $ by 1 and $ a_{i+1} $ by 1). We must cover exactly $ a_i $ pizzas on day $ i $, using any number of these operations, and **no active coupon may remain after day $ n $** (i.e., no coupon can extend beyond day $ n $). Define: - Let $ x_i \in \mathbb{Z}_{\geq 0} $ be the number of **discounts** used on day $ i $. - Let $ y_i \in \mathbb{Z}_{\geq 0} $ be the number of **coupons** covering days $ i $ and $ i+1 $, for $ i = 1, 2, \dots, n-1 $. Then, for each day $ i $, the total number of pizzas covered is: $$ a_i = 2x_i + y_{i-1} + y_i $$ with boundary conditions: - $ y_0 = 0 $ (no coupon before day 1), - $ y_n = 0 $ (no coupon after day $ n $). We must determine whether there exist non-negative integers $ x_1, \dots, x_n $ and $ y_1, \dots, y_{n-1} $ satisfying the above system. --- **Formal Problem Statement:** Given $ a_1, a_2, \dots, a_n \in \mathbb{Z}_{\geq 0} $, determine whether there exist non-negative integers $ x_1, \dots, x_n $ and $ y_1, \dots, y_{n-1} $ such that for all $ i = 1, \dots, n $: $$ a_i = 2x_i + y_{i-1} + y_i $$ where $ y_0 = y_n = 0 $. --- **Equivalently, we can solve greedily:** We process days left to right. For day $ i $, the number of pizzas already covered by coupons from day $ i-1 $ is $ y_{i-1} $. The remaining pizzas to cover on day $ i $ is $ r_i = a_i - y_{i-1} $. This must be non-negative. Then, we can use: - As many discounts as possible (i.e., subtract even parts), - The remainder (if any) must be covered by starting new coupons to day $ i+1 $, i.e., set $ y_i = r_i \mod 2 $, and use $ x_i = \lfloor r_i / 2 \rfloor $. But since coupons must end at day $ n $, we require $ y_n = 0 $, so after processing day $ n $, we must have $ r_n = a_n - y_{n-1} $ even and non-negative. Thus, the algorithm is: 1. Initialize $ y = 0 $ (coupon carried over from previous day). 2. For $ i = 1 $ to $ n $: - $ r = a_i - y $ - If $ r < 0 $: return NO. - If $ r $ is odd and $ i < n $: set $ y = 1 $ (use one coupon to next day), and $ x_i = (r - 1)/2 $. - If $ r $ is odd and $ i = n $: return NO (cannot leave active coupon). - If $ r $ is even: set $ y = 0 $, $ x_i = r/2 $. 3. If we complete the loop, return YES. But note: we may choose to use *more* coupons than strictly necessary? Actually, no — we must cover *exactly* $ a_i $, and we cannot overbuy. So the above greedy is forced: at each day, the leftover after subtracting incoming coupons must be covered by discounts and outgoing coupons, and since discounts cover 2, the parity of the leftover forces the number of outgoing coupons. Thus, the **necessary and sufficient condition** is: > There exists a sequence $ y_1, \dots, y_{n-1} \in \{0,1\} $ such that for all $ i \in \{1, \dots, n\} $, > $ a_i - y_{i-1} - y_i \geq 0 $ and is even, > with $ y_0 = y_n = 0 $. And we can compute this greedily: Let $ y = 0 $. For $ i = 1 $ to $ n $:   $ r = a_i - y $   If $ r < 0 $: return NO   If $ i == n $:     if $ r $ is odd: return NO     else: continue   Else:     if $ r $ is odd: $ y = 1 $     else: $ y = 0 $ If we finish: return YES. --- **Final Formal Statement:** Let $ a = (a_1, \dots, a_n) \in \mathbb{Z}_{\geq 0}^n $. Define a sequence $ y_0, y_1, \dots, y_n \in \{0,1\} $ with $ y_0 = y_n = 0 $, and for each $ i \in \{1, \dots, n\} $, define: $$ r_i = a_i - y_{i-1} $$ Then, $ y_i = r_i \mod 2 $ for $ i < n $, and $ y_n = 0 $. We require $ r_i \geq 0 $ for all $ i $, and $ r_n $ even. The system is feasible **if and only if** the greedy assignment yields $ r_i \geq 0 $ for all $ i $ and $ r_n $ even. Thus, the problem reduces to checking feasibility of this greedy propagation. --- **Mathematical Condition:** There exists a sequence $ y_1, \dots, y_{n-1} \in \{0,1\} $ such that: - $ a_1 - y_1 \geq 0 $ and even, - $ a_i - y_{i-1} - y_i \geq 0 $ and even for $ i = 2, \dots, n-1 $, - $ a_n - y_{n-1} \geq 0 $ and even. with $ y_0 = y_n = 0 $. This is equivalent to the greedy algorithm above.