Description

给定一个长度为 $n$ 的数列 $a_{1\ldots n}$，其中 $\forall i,a_i\in\{1,-1\}$. 这个数列可以被划分为若干个连续段，对于某一段 $a_{l\ldots r}$，定义这一段的权值为

你要将其划分为若干个连续段（请注意是划分而不是选取，换句话说，$a$ 的每一项都应该恰好属于一个连续段中），使得所有段的权值的和为 $0$.

若这样的划分方案不存在，输出 DNE.

Format

Input

第一行一个正整数 $n\quad(1\leq n\leq 10^6)$ 表示序列的长度。

第二行 $n$ 个整数，第 $i$ 个数表示 $a_i\quad(a_i\in\{-1,1\})$.

Output

若无解，输出仅一行一个字符串 DNE.

否则，第一行输出一个正整数 $k$，表示你划分的段数。

随后每一行输出两个正整数 $l_i,r_i$，表示第 $i$ 段为 $a_{l_i\ldots,r_i}$. 输出段的顺序可以任意。

你需要保证数列中每个数恰好被分入了一段，且对于每一段 $l_i,r_i$ 有 $1\leq l_i\leq r_i\leq n$.

Samples

6
-1 1 -1 1 -1 1

2
1 3
4 6

Limitation

1s, 256MiB.