**Problem Link:** contest, practice

**Difficulty:** Simple

**Pre-requisites:** Sorting, Scanline

**Problem:**

Given a permutation **P** of **N** integers. Also, given **M** ranges (**L _{i}**,

**R**). You are allowed to perform the next procedure a finite number of times: choose any given range (

_{i}**L**,

**R**) and shuffle subsegment

**P[L…R]**arbitrarily. You are to determine if it’s possible to obtain

**P**out of the

**1, 2, …, N**permutation.

**Explanation:**

At first, let’s assume, that all the ranges don’t intersect(it means, that for any two given ranges **A** = (**L _{1}**,

**R**) and

_{1}**B**= (

**L**,

_{2}**R**) there’s no integer

_{2}**K**, that simultaneously belongs to

**A**and

**B**). If that’s not true, than we can unite some of the ranges with a help of scanline algorithm(check out Setter’s and Tester’s solutions if you are not familiar with that algorithm).

So, all the ranges don’t intersect. Then the solution is pretty easy: the answer is “Possible” if and only if **i** and **P _{i}** belong to the same range for each

**i**.

It’s may be not clear why it’s OK to unite some ranges. But it’s not hard to prove the correctness of this approach: we can construct permutation **P** element-by-element, starting with putting **P _{1}** on the first place and so on. We can perform the putting stage of the algorithm with some greedy approach.

Total complexity is O( **N log N** ) per testcase.

Please, check out Setter’s and Tester’s solutions for your better understanding.

**Setter’s Solution:** link

**Tester’s Solution:** link