<gh_stars>0
class Solution:
    # @param A : list of integers
    # @return a list of integers
    def solve(self, A):
        if len(A) < 2:
            # empty check
            return A
        i = 0
        while i < len(A):
            temp = -1
            if (i % 2 == 0 and A[i] >= 0) or (i % 2 != 0 and A[i] < 0):
                # 1st out of place
                temp = i
            else:
                i += 1
                continue
            if A[temp] >= 0:
                # find negative and insert to i
                while temp < len(A) and A[temp] >= 0:
                    temp += 1
            else:
                # find positive and insert to i
                while temp < len(A) and A[temp] < 0:
                    temp += 1
            if temp < len(A): A.insert(i, A.pop(temp))
            i += 2
        return A


# a = [5, -17, -100, -11, 5, 6, 7, -80, -90, -11, -100, 0, -200, 200, 5, 6, 10,11,12,13,14,15]
a = [-23, -24, -1, -25, 22, 1, 22, -28, 0, 3, -24, 6, 0, -23, 7, 5, 17, 18, 14, 5, 20, -25, -13,
     26, 13, -29, -7, 5, -4, 9, -30, 20, 11, -11, 22, 1, -19, 24, -15, 3, 17, -28, 30, -20, 30,
     20, -14, -28, 18, 10, -28, -25, -12, -21, 15, 0, 6, -15, 25, -25, 13, -24, 14, -22, 9, -23,
     5, -12, 6, -11, -12, 10, -12, -2, -8, 4, 17, -11, -4, 18, 11, -1, 1, -21, 14, -11, -18, 19,
     17, 9, -5, 8, -3, -6, -18, 19, -18, -5, -8, -29, -4, -27, 12, 2, 30, 8, 19, 11, -16, 20,
     -22, 8, -27, -15, -12, 9, -10, 10, 22, 16, -9, -12, 9, -28, 2, 18, -28, -26, 21, 27, -18,
     -13, -17, 20, 2, 11, 16, -11]

b = (Solution().solve(a))
print(len(b) == len(a))
print(b)
c = [-23, 22, -24, 1, -1, 22, -25, 0, -28, 3, -24, 6, -23, 0, -25, 7, -13, 5, -29, 17, -7, 18, -4, 14, -30, 5, -11, 20,
     -19, 26, -15, 13, -28, 5, -20, 9, -14, 20, -28, 11, -28, 22, -25, 1, -12, 24, -21, 3, -15, 17, -25, 30, -24, 30,
     -22, 20, -23, 18, -12, 10, -11, 15, -12, 0, -12, 6, -2, 25, -8, 13, -11, 14, -4, 9, -1, 5, -21, 6, -11, 10, -18, 4,
     -5, 17, -3, 18, -6, 11, -18, 1, -18, 14, -5, 19, -8, 17, -29, 9, -4, 8, -27, 19, -16, 12, -22, 2, -27, 30, -15, 8,
     -12, 19, -10, 11, -9, 20, -12, 8, -28, 9, -28, 10, -26, 22, -18, 16, -13, 9, -17, 2, -11, 18, 21, 27, 20, 2, 11,
     16]
# Solution for a
print(c)
print(b == c)

class Solution:
    # @param A : list of integers
    # @return a list of integers
    def solve(self, A):
        if len(A) < 2:
            # empty check
            return A
        i = 0
        while i < len(A):
            temp = -1
            if (i % 2 == 0 and A[i] >= 0) or (i % 2 != 0 and A[i] < 0):
                # 1st out of place
                temp = i
            else:
                i += 1
                continue
            if A[temp] >= 0:
                # find negative and insert to i
                while temp < len(A) and A[temp] >= 0:
                    temp += 1
            else:
                # find positive and insert to i
                while temp < len(A) and A[temp] < 0:
                    temp += 1
            if temp < len(A): A.insert(i, A.pop(temp))
            i += 2
        return A


# a = [5, -17, -100, -11, 5, 6, 7, -80, -90, -11, -100, 0, -200, 200, 5, 6, 10,11,12,13,14,15]
a = [-23, -24, -1, -25, 22, 1, 22, -28, 0, 3, -24, 6, 0, -23, 7, 5, 17, 18, 14, 5, 20, -25, -13,
     26, 13, -29, -7, 5, -4, 9, -30, 20, 11, -11, 22, 1, -19, 24, -15, 3, 17, -28, 30, -20, 30,
     20, -14, -28, 18, 10, -28, -25, -12, -21, 15, 0, 6, -15, 25, -25, 13, -24, 14, -22, 9, -23,
     5, -12, 6, -11, -12, 10, -12, -2, -8, 4, 17, -11, -4, 18, 11, -1, 1, -21, 14, -11, -18, 19,
     17, 9, -5, 8, -3, -6, -18, 19, -18, -5, -8, -29, -4, -27, 12, 2, 30, 8, 19, 11, -16, 20,
     -22, 8, -27, -15, -12, 9, -10, 10, 22, 16, -9, -12, 9, -28, 2, 18, -28, -26, 21, 27, -18,
     -13, -17, 20, 2, 11, 16, -11]

b = (Solution().solve(a))
print(len(b) == len(a))
print(b)
c = [-23, 22, -24, 1, -1, 22, -25, 0, -28, 3, -24, 6, -23, 0, -25, 7, -13, 5, -29, 17, -7, 18, -4, 14, -30, 5, -11, 20,
     -19, 26, -15, 13, -28, 5, -20, 9, -14, 20, -28, 11, -28, 22, -25, 1, -12, 24, -21, 3, -15, 17, -25, 30, -24, 30,
     -22, 20, -23, 18, -12, 10, -11, 15, -12, 0, -12, 6, -2, 25, -8, 13, -11, 14, -4, 9, -1, 5, -21, 6, -11, 10, -18, 4,
     -5, 17, -3, 18, -6, 11, -18, 1, -18, 14, -5, 19, -8, 17, -29, 9, -4, 8, -27, 19, -16, 12, -22, 2, -27, 30, -15, 8,
     -12, 19, -10, 11, -9, 20, -12, 8, -28, 9, -28, 10, -26, 22, -18, 16, -13, 9, -17, 2, -11, 18, 21, 27, 20, 2, 11,
     16]
# Solution for a
print(c)
print(b == c)
# @param A : list of integers # @return a list of integers # empty check # 1st out of place # find negative and insert to i # find positive and insert to i # a = [5, -17, -100, -11, 5, 6, 7, -80, -90, -11, -100, 0, -200, 200, 5, 6, 10,11,12,13,14,15] # Solution for a