CF339E Three Swaps

Xenia the horse breeder has $ n $ $ (n>1) $ horses that stand in a row. Each horse has its own unique number. Initially, the $ i $ -th left horse has number $ i $ . That is, the sequence of numbers of horses in a row looks as follows (from left to right): 1, 2, 3, $ ... $ , $ n $ . Xenia trains horses before the performance. During the practice sessions, she consistently gives them commands. Each command is a pair of numbers $ l,r $ $ (1

The first line contains an integer $ n $ $ (2

The first line should contain integer $ k $ $ (0