CF1793F Rebrending

Kostya and Zhenya — the creators of the band "Paper" — after the release of the legendary album decided to create a new band "Day movers", for this they need to find two new people. They invited $ n $ people to the casting. The casting will last $ q $ days. On the $ i $ th of the days, Kostya and Zhenya want to find two people on the segment from $ l_i $ to $ r_i $ who are most suitable for their band. Since "Day movers" are doing a modern art, musical skills are not important to them and they look only at other signs: they want the height difference between two people to be as small as possible. Help them, and for each day, find the minimum difference in the growth of people from the casting on this segment!

N/A

N/A

In the first example, the minimum difference on the segment $ [1, 2] $ is $ 2 $ , on the segment $ [2, 3] $ — $ 1 $ , on the segment $ [1, 3] $ is also $ 1 $ . In the third example, the numbers with the minimum difference on the segment $ [4, 6] $ are $ 3 $ and $ 5 $ ( $ 5 - 3 = 2 $ ). On the segment $ [1, 2] $ , the numbers with the minimum difference are $ 2 $ and $ 6 $ ( $ 6 - 2 = 4 $ ). On the segment $ [3, 6] $ , the numbers with the minimum difference are $ 1 $ and $ 3 $ ( $ 3 - 1 = 2 $ ). On the segment $ [1, 3] $ , the minimum difference is formed by the numbers $ 1 $ and $ 2 $ ( $ 2 - 1 = 1 $ ).