CF1167E Range Deleting

You are given an array consisting of $ n $ integers $ a_1, a_2, \dots , a_n $ and an integer $ x $ . It is guaranteed that for every $ i $ , $ 1 \le a_i \le x $ . Let's denote a function $ f(l, r) $ which erases all values such that $ l \le a_i \le r $ from the array $ a $ and returns the resulting array. For example, if $ a = [4, 1, 1, 4, 5, 2, 4, 3] $ , then $ f(2, 4) = [1, 1, 5] $ . Your task is to calculate the number of pairs $ (l, r) $ such that $ 1 \le l \le r \le x $ and $ f(l, r) $ is sorted in non-descending order. Note that the empty array is also considered sorted.

N/A

N/A

In the first test case correct pairs are $ (1, 1) $ , $ (1, 2) $ , $ (1, 3) $ and $ (2, 3) $ . In the second test case correct pairs are $ (1, 3) $ , $ (1, 4) $ , $ (2, 3) $ , $ (2, 4) $ , $ (3, 3) $ and $ (3, 4) $ .