CF1707E Replace

You are given an integer array $ a_1,\dots, a_n $, where $ 1\le a_i \le n $ for all $ i $. There's a "replace" function $ f $ which takes a pair of integers $ (l, r) $, where $ l \le r $, as input and outputs the pair $f((l, r))=\left(\min\{a_l,a_{l+1},\dots,a_r\},\max\{a_l,a_{l+1},\dots,a_r\}\right)$. Consider repeated calls of this function. That is, from a starting pair $(l, r)$ we get $ f((l, r)) $, then $ f(f((l, r))) $, then $ f(f(f((l,r)))) $, and so on. Now you need to answer $ q $ queries. For the $ i $-th query you have two integers $ l_i $ and $ r_i $ $(1\le l_i\le r_i\le n)$. You must answer the minimum number of times you must apply the "replace" function to the pair $(l_i,r_i)$ to get $ (1, n) $, or report that it is impossible.

N/A

N/A

In the first example, $ n=5 $ and $ a=[2,5,4,1,3] $ . For the first query: $ (4,4)\to(1,1)\to(2,2)\to(5,5)\to(3,3)\to(4,4)\to\ldots $ , so it's impossible to get $ (1,5) $ . For the second query, you already have $ (1,5) $ . For the third query: $ (1,4)\to(1,5) $ . For the fourth query: $ (3,5)\to(1,4)\to(1,5) $ . For the fifth query: $ (4,5)\to(1,3)\to(2,5)\to(1,5) $ . For the sixth query: $ (2,3)\to(4,5)\to(1,3)\to(2,5)\to(1,5) $ .