题目内容

中转仓今晚只有一条暂存滑轨，滑轨按栈工作：后进的货先出。值班员必须按货号从小到大出库，并记下唯一的入轨、出库动作；若做不到就在日志里写失败标记。

共有 $k$ 件货按到达顺序经过主道，第 $i$ 件的货号是 $v_i$。$v$ 是 $1 \sim k$ 的一个排列。出库顺序必须恰好是 $1,2,\dots,k$。

每件货到达时，值班员必须立刻做下面两种动作之一：

• I：把它推进暂存栈；
• 若规则允许，之后用 O 弹出栈顶出库。

任意时刻只要栈顶正好是下一个该出的货号，就必须立刻 O 出库。可以证明：能成功时，动作序列是唯一的。

请判断能否按号出完。能则输出由 I 和 O 组成的动作串（恰好 $k$ 个 I 和 $k$ 个 O）；不能则输出 N。

货件数满足 $1 \le k \le$ 200000。

输入描述

第一行一个正整数 $k$（$1 \le k \le$ 200000），表示货件数。

第二行 $k$ 个正整数 $v_1,v_2,\dots,v_k$，保证是 $1 \sim k$ 的排列。

输出描述

若存在合法方案，输出一行由 I 和 O 组成的字符串；否则输出一行一个字符 N。

样例1

输入

4
3 1 2 4

输出

IIOIOOIO

说明

3、1 入栈后弹出 1，再让 2 入栈并连续弹出 2、3，最后 4 入栈再出库。

样例2

输入

3
2 3 1

输出

N

说明

2、3 入栈后，1 再入再出，栈顶变成 3，下一个该出的是 2，卡死。

样例3

输入

1
1

输出

IO

说明

只有一件货，入栈后立刻出库。