Frog Lily Pad Non‐Consecutive Jump Assignment

You are given an integer n and a sequence of n lily pads with values \(x_1, x_2, \dots, x_n\) (with \(1 \le i \le n\)) in strictly increasing order. Three frogs are available, numbered 1, 2, and 3.

For every pair of lily pads \((i,j)\) with \(1 \le i < j \le n\), you must assign it to one of the three frogs. Note that a frog may be assigned many pairs.

A frog can jump from lily pad \(i\) to lily pad \(j\) if and only if \(x_j\) is divisible by \(x_i\) (i.e. \(x_j \bmod x_i = 0\)) and the pair \((i,j)\) is assigned to that frog. A frog is said to have "three consecutive jumps" if there exists indices \(i < j < k < l\) such that the pairs \((i,j)\), \((j,k)\), and \((k,l)\) are all assigned to the same frog and the divisibility conditions hold: \[ x_j \bmod x_i = 0,\quad x_k \bmod x_j = 0,\quad x_l \bmod x_k = 0. \] Your task is to output an assignment of every pair \((i,j)\) to a frog (denoted by its number 1, 2, or 3) such that no frog can ever make three consecutive jumps (i.e. no such chain exists for any frog).

If there are pairs \((i,j)\) for which \(x_j\) is not divisible by \(x_i\), you can assign any frog number arbitrarily because such pairs do not allow a jump.

If multiple valid assignments exist, print any one.

inputFormat

The input begins with a line containing a single integer n (the number of lily pads). The next line contains n space‐separated integers \(x_1, x_2, \dots, x_n\) which form a strictly increasing sequence.

outputFormat

If a valid assignment exists, first print a line containing the word YES. Then print a line with an integer m representing the total number of pairs (which is \(\frac{n(n-1)}{2}\)). After that, print m lines, each containing three integers: i j f, meaning that the pair of lily pads \((i, j)\) is assigned to frog f (where f is 1, 2, or 3). It is guaranteed that any valid assignment will be accepted.

sample

4
1 2 3 6

YES
6
1 2 2
1 3 1
1 4 3
2 3 1
2 4 2
3 4 3