解题思路

使用栈模拟算法。

从左到右扫描原数组，栈中维护已经处理完成的部分。

设当前元素为 $x$：

• 如果栈非空，且栈顶元素等于 $x$：

题目内容

给定一个长度为 $n$ 的整数数组。

请你从左到右对数组进行处理，处理规则如下：

1. 如果遇到两个相邻且相同的偶数，则在这两个偶数中间插入它们的和。
2. 如果遇到两个相邻且相同的奇数，则删除这两个奇数，然后在原位置插入它们的和。
3. 处理过程中产生的新元素，也需要继续参与后续判断。

请输出处理完成后的数组。

输入描述

输入共两行。

• 第一行包含整数 $n$，表示数组长度。
• 第二行包含 $n$ 个整数，表示数组中的元素。

输出描述

输出共一行，包含若干个整数，表示处理完成后的数组。

相邻两个整数之间用一个空格隔开。

数据范围

• $1 \le n \le 100000$
• $1 \le a_i \le 10^9$

输入样例

9
2 2 3 3 6 4 5 5 6

输出样例

2 4 2 6 12 6 4 10 6

样例解释

原数组为：

2 2 3 3 6 4 5 5 6

从左到右处理：

• 2 2 是两个相邻且相同的偶数，所以在它们中间插入 2 + 2 = 4，得到 2 4 2
• 3 3 是两个相邻且相同的奇数，所以删除这两个 3，并插入 3 + 3 = 6
• 新生成的 6 与后面的 6 相邻且相同，并且都是偶数，所以在它们中间插入 6 + 6 = 12
• 5 5 是两个相邻且相同的奇数，所以删除这两个 5，并插入 5 + 5 = 10

因此，处理后的数组为：

2 4 2 6 12 6 4 10 6