Local or Global

Difficulty: 1300 4000 ms 128 MB

math implementation

A permutation's LOCAL inversions are adjacent ones (a_i > a_i+1); GLOBAL inversions are any i < j with a_i > a_j. Print YES if every global inversion is local (the two counts coincide).

Input: the first line has N; the second line has a permutation of 1..N.

Output: YES or NO.

Constraints:

• 1 ≤ N ≤ 10⁵

Sample Tests

3
1 3 2

YES

3
3 1 2

NO

Read the Editorial