بچه‌ی آقا داوود همه‌ی $N$ مداد رنگی‌‌اش را بر حسب رنگشان مرتب کرده است. مداد رنگی‌ها از چپ به راست با اعداد $1$ تا $N$ نام‌گذاری شده‌اند. او در $M$ مرحله هر بار یکی از اعمال زیر را روی دنباله‌ی مداد رنگی‌هایش انجام می‌دهد:
منظور از ترتیب اولیه در عملیات‌ها ترتیبی است که هیچ عملیاتی روی آن انجام نشده است.
پس از هر عملیات بچه‌ی آقا داوود از او می‌خواهد تا میزان به هم ریختگی ترتیب فعلی مداد رنگی‌ها را به او بگوید. می‌دانیم به‌هم‌ریختگی یک دنباله از مداد رنگی‌ها برابر با تعداد جفت مداد رنگی‌هایی است که عکس ترتیب اولبه‌شان در دنباله ظاهر شده‌اند. به عبارتی دیگر شما باید به آقا داوود کمک کنید تا تعداد نابجایی‌های دنباله‌ی مداد رنگی‌ها را در هر لحظه چاپ کند. آقا داوود پس از کمی بازی با بچه‌اش فهمیده‌است که هر دو بازه‌ای که بچه‌اش بر روی آن‌ها عملیات انجام می‌دهد گوگولی هستند. دو بازه گوگولی هستند اگر یا با هم اشتراک نداشته باشند یا یکی درون دیگری باشد. به عبارتی دیگر به ازای هر دو بازه‌ی $[a,b]$ و $[c,d]$ در ورودی دست کم یکی از عبارات زیر برقرار است:
<, >} آمده است. حرف < به معنای عملیات نوع اول و حرف > به معنای عملیات نوع دوم است. خروجی شامل $M$ سطر است که سطر $i$-ام به هم ریختگی مدادرنگی ها بعد از عملیات $i$-ام است.
| ورودی نمونه | خروجی نمونه |
|---|---|
| 5 4 1 3 > 4 5 > 1 3 < 1 5 < | 3 4 1 0 |