Иахуб нэгэн сонирхолтой тоглоом тоглож байв. Одоогоор түүнд $1, 2, 3, ... , n$ дугаарлагдсан $n$ ширхэг хайрцагнууд байв. Хайрцаг бүрт $a_1, a_2, ... , a_n$ дарааллаар тодорхойлогдсон хэдэн ширхэг чихэр байсан. $a_k$ тоо $k$ хайрцган дахь чихэрний тоо ширхэгийг илэрхийлнэ.

Тоглоомны зорилго нь бүх чихрийг яг хоёр хайрцганд шилжүүлэх юм. Үлдсэн $n-2$ ширхэг хайрцгууд $0$ чихэр агуулах ёстой. Иахуб хэд хэдэн үйлдэл хийх ($0$ байж болно) зөвшөөрөлтэй. Хөдөлгөөн бүрээр тэр $i$ ба $j$ гэсэн $a_i ≤ a_j$ байх хоёр ялгаатай хайрцаг сонгож авна. Тэгээд Иахуб $j$ хайрцагнаас $i$ хайрцаг руу яг $a_i$ чихэр шилжүүлнэ. Хэрэв хайрцагнууд тэнцүү тооны чихэртэй байвал $j$ дугаартай хайрцаг хоосон болох нь тодорхой.

Чиний даалгавар бол Иахубд түүнд тоглоомны зорилгыг биелүүлэх үйлдлүүдийг зааж өгөх юм. Хэрэв Иахуб өгөгдсөн хайрцагнуудаар тоглоод бодлогод хожиж чадахгүй байвал $-1$ гэж хэвлээрэй. Хэрэв шийд оршин байгаа нөхцөлд та заавал шийдийн хамгийн бага утгыг хэвлэх шаардлагагүйг анхаарна уу.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($3 ≤ n ≤ 1000$) байна. Дараагийн мөр $n$ ширхэг дарааллын гишүүд болох сөрөг биш $a_1, a_2, ... , a_n$ тоонуудыг агуулна. $a$ дараалал дахь бүх тоонуудын нийлбэр $10^6$ аас их байх нь батлагдсан болно.

Гаралт

Шийд оршин байхгүй тохиолдолд $-1$ хэвлээрэй. Өөр тохиолдолд гаралтын эхний мөрөнд шийдийн нийт үйлдлийн тоог илэрхийлэх $c$ ($0 ≤ c ≤ 10^6$) бүхэл тоог хэвлэнэ. Дараагийн $c$ мөр тус бүр $i$ ба $j$ ($1 ≤ i, j ≤ n$, $i ≠ j$) гэсэн $2$ ширхэг бүхэл тоонуудыг агуулах хэрэгтэй. $k$ дугаар мөрөн дэх $i$, $j$ бүхэл тоонууд бол $k$ дугаар үйлдлийг $j$ хайрцагнаас $i$ хайрцаг руу чихэр шилжүүлэх үйлдэл болохыг илэрхийлж байгаа юм.

For the first sample, after the first move the boxes will contain 3, 12 and 3 candies. After the second move, the boxes will contain 6, 12 and 0 candies. Now all candies are in exactly 2 boxes.

For the second sample, you can observe that the given configuration is not valid, as all candies are in a single box and they should be in two boxes. Also, any move won't change the configuration, so there exists no solution.

For the third sample, all candies are already in 2 boxes. Hence, no move is needed.