# 牌组前缀的可行划分

预估时间限制：0.5 秒。内存限制：128 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

整理员按数字逐步展开一套牌。每加入一种数字，就检查当前所有牌能否组成普通组合，或者组成普通组合再加唯一的一对。

(本故事由GPT-6重写)

## 形式化问题描述

只有一种牌，数字为 $1,\ldots,n$ ，数字 $i$ 的牌有 $a_i$ 张。对于每个 $i$ ，只取数字 $1,\ldots,i$ 的全部牌，分别判断：

1. 能否划分成任意多个三张顺子和任意多个三张同牌组？
2. 能否划分成上述组合，再加上**恰好一组**两张同数字的牌？

三张顺子包含三个连续数字，每个数字一张；三张同牌组的三个数字相同。顺子和三张同牌组都允许重复。每种判断都要求所取的每张牌恰好使用一次，不得使用数字大于 $i$ 的牌。不同前缀的判断彼此独立。

## 输入格式

第一行一个整数 $n$ .第二行 $n$ 个整数 $a_1,\ldots,a_n$ .

## 输出格式

输出 $n$ 行，第 $i$ 行两个用空格分隔的整数，依次表示上述两个判断。可以划分输出 `1` ，否则输出 `0` .

## 样例

### 样例 1

### 输入

```text
6
1 1 1 2 2 2
```

### 输出

```text
0 0
0 0
1 0
0 1
0 0
1 0
```

### 样例 2

### 输入

```text
1
2
```

### 输出

```text
0 1
```

### 样例 3

### 输入

```text
3
3 3 3
```

### 输出

```text
1 0
1 0
1 0
```

## 样例解释

第一组的第三个前缀是一个顺子；第四个前缀可以在此基础上增加数字四的一对。第六个前缀还可用两个重复的 $(4,5,6)$ 顺子。第二组只有一对，不能无对子划分。第三组每个前缀都能分别使用同牌三张组，总牌数是三的倍数，因此不能再恰好包含一对。

## 数据范围与保证

$1\le n\le5\times10^6$ , $1\le a_i\le10^9$ .

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |