This is the problem asked yesterday in icpc kanpur regionals.How should approach this problem?

Problem Statement You have an array A (1-indexed) of N integers. You can perform any number of operations on this array. An operation goes like this,

(1) You pick an index i such that 1 ≤ i ≤ n-2 and a[i] + a[i+2] > a[i+1]

(2) Then you swap a[i] and a[i+2]

You have to output if you can sort the array in non-decreasing order after performing any number of operations. Constraints 1 ≤ T ≤ 10^5 1 ≤ N ≤ 10^5 1 ≤ Sum of N over all testcases ≤ 10^5 1 ≤ Ai ≤ 10^9