Bu gün Vasyanı sinfi təmizləməyə məcbur etdilər. Nizamnamə qayda yaradır, o qərara gəldi ki, indi zərərlərin qarşılığının ödənilməsi üçün haradasa nizamsızlıq yaratmalıdır. Elə burada onun gözlərinə müəllimi tərəfindən lövhəyə yazılmış 1-dən n-ə qədər ədədlərin yerdəyişmələri sataşdı. Qeyd edək ki, 1-dən n-ə qədər ədədlərin yerdəyişməsi hər birinin yalnız bir dəfə rast gəlindiyi n ədəd ehtiva edən ardıcıllıqdır.

Vasya hesab edir ki, üç ardıcıl gələn element əgər artan və ya azalan sıra ilə sıralanmışdırlarsa, deməli onlar sıralıdır. O yerdəyişməni o zaman nizamsız adlandırır ki, sıralı olan heç bir ardıcıl gələn üç element olmasın.

Vasya yerdəyişməni nizamsız etmək üçün onu dəyişdirmək qərarına gəldi. Bunun üçün o yerdəyişmədə n-dən çox olmayaraq iki qonşu elementin yerini dəyişdirmək qərarına gəldi.

Müəllimin gələrək və onu təmizlik yerinə lazımsız işlərlə məşğul olduğu üçün danlamasına yol verməmək üçün Vasyaya yerdəyişməni nizamsız hala salmaqda kömək edin.

Giriş verilənləri

Giriş faylında lövhədə yazılmış cari yerdəyişmə verilir. İlk sətir yerdəyişmənin uzunluğunu ifadə edən tam n (3 ≤ n ≤ 1000) ədədini ehtiva edir. İkinci sətir hər biri 1-dən n-ə qədər diapazonda yerləşən n sayda müxtəlif ədədlər ehtiva edir.

Çıxış verilənləri

İlk sətirdə Vasyanın etməli olduğu əməliyyatların sayını ifadə edən k ədədi verin. Növbəti sətirdə əməliyyatlar ardıcıllığının özünü ifadə edən k ədədini verin. Əgər növbəti addımda yerdəyişmənin i-ci və i + 1-ci elementlərinin yerini dəyişdirmək lazım gələrsə, i ədədini vermək lazımdır.

Əgər bir neçə cavab olarsa, siz onlardan istənilən birini verə bilərsiniz. Nəzərə alın ki, siz əməliyyatların sayını azaltmaq məcburiyyətində deyilsiniz. Kifayətdir ki, onların sayı n-i aşmasın. Əgər həll yoxdursa, -1 ədədini verin.

Misalın şərhi

Birinci misalda yerdəyişmə növbəti şəkildə olacaq: (**1 2 3 4 5**) → (**1 2 3 5 4**) → (**2 1 3 5 4**) → (**2 3 1 5 4**). İkinci misalda verilmiş cavab, həmçinin doğrudur. Üçüncü misalda yerdəyişmə nizamsızdır və hər bir şeyi dəyişdirmək lazım deyil.