Anti Binary Search Tree

题号：NC217612
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

For a binary tree, let $\mathbb{V}$ be the set of all its vertices and $K(v)$ be the key of a vertex $v \in \mathbb{V}$ . We say this binary tree is an anti binary search tree if for all $v \in \mathbb{V}$ , at least one of the following statement is true:

Vertex $v$ is a leaf;
Vertex $v$ has a left child $l$ and $K(l) > K(v)$ ;
Vertex $v$ has a right child $r$ and $K(r) < K(v)$ .

Given $n$ integers $a_1, a_2, \cdots, a_n$ , please construct an anti binary search tree such that the multi-set of the keys of all vertices in the tree equals to the multi-set of these $n$ integers, and that the height of the tree does not exceed $\lceil\log_2 n\rceil$ , where $\lceil x \rceil$ indicates the smallest integer that is not smaller than $x$ .

Recall that the height of the tree is the maximum number of edges between the root of the tree and any vertex on the tree. That is to say, a tree with only one vertex has a height of 0, and a tree with two vertices has a height of 1.

输入描述:

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ( $1 \le n \le 10^5$ ) indicating the number of given integers.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ( $1 \le a_i \le n$ ) indicating the given integers.

It's guaranteed that the sum of $n$ of all test cases will not exceed $5 \times 10^5$ .

输出描述:

For each test case, if such anti binary search tree exists, first output "Yes" (without quotes) in one line, then output $n$ lines indicating the constructed binary tree. For these $n$ lines, the $i$ -th line contains 3 integers $k_i$ , $l_i$ and $r_i$ separated by a space, indicating the key of the $i$ -th vertex, the index of its left child and the index of its right child. $l_i = 0$ indicates that this vertex does not have a left child, while $r_i = 0$ indicates that this vertex does not have a right child. Vertex number 1 must be the root. If there are multiple valid answers, you can output any of them.

If no such anti binary search tree exists, just output "No" (without quotes) in one line.

示例1

输入

复制

输出

复制