题目描述

有一个由 $N$ 个整数组成的序列 $a_1,a_2, \cdots ,a_N$。序列 $b_1,b_2, \cdots ,b_L$ 是给定序列的子序列，如果

1. 对于每个 $i$ （$1 \leq i \leq L$），存在这样的 $j$ （$1 \leq j \leq N$），使得 $b_i= a_j$；
2. 对于每个 $i_1$ 和 $i_2$ 使得 $i_1 < i_2$，$b_{i1} = a_{j1}$，$b_{i2} = a_{j2}$，关系 $j_1 < j_2$ 是有效的。

序列 $b_1,b_2, \cdots,b_L$ 是非递增的，如果对于每个 $i$（$1 \le i < L$），$b_i \le b_{i+1}$。
序列 $b_1,b_2, \cdots,b_L$ 是非递减的，如果对于每个 $i$（$1 \le i < L$），$b_i \le b_{i+1}$。
给定的序列称为 NICE，如果我们可以选择该序列的 $K$ 个子序列使得：

1. 每个子序列至少有 $2$ 个成员，
2. 每个子序列要么不增加要么不减少，
3. 给定序列的每个成员直接属于一个子序列。

找出给定序列的最小可能 $K$。

输入格式

第一行包含一个整数为 $N$ 的值，接下来的 $N$ 行包含序列成员的值（每行一个整数，对于每个 $j$（$1 \le a_j \le 100$））。

输出格式

输出数据必须包含：

1. 第一行中 $K$ 的值，
2. 将给定序列划分为 $K$ 个子序列的一个示例（即必须有 $N$ 行，每行包含子序列的 $a_j$ 和其 $a_j$ 属于的 索引（$1 \le$ 索引 $\le K$））。

如果给定的序列不是 NICE，则输出文件的第一行必须仅包含 $0$。

6
12
33
97
18
15
33

2
12 1
33 1
97 2
18 2
15 2
33 1

1
88

0

4
77
22
22
11

1
77 1
22 1
22 1
11 1

提示

数据规模与约定

对于 $100 \%$ 的数据，$1 \le N \le 25$，$0 < K \le N$。

样例说明

样例一中，子序列是 $12，33，33$ 和 $97，18，15$。

分值说明

本题分值按 BOI 原题设置，满分 $40$ 。

题目说明

来源于 Baltic Olympiad in Informatics 2000] 的 Day 1:A NICE SEQUENCE。
由 @求学的企鹅 翻译整理。