import copy


def permutationwithparity(n):
   """Returns a list of all permutation of n integers, with its first element being the parity"""
   if (n == 1):
      result = [[1,1]]
      return result
   else:
      result = permutationwithparity(n-1)
      newresult = []
      for shorterpermutation in result:
         for position in range(1,n+1):
            parity = shorterpermutation[0]
            for swaps in range(n-position):
               parity = - parity
            newpermutation = copy.deepcopy(shorterpermutation)
            newpermutation.insert(position,n)
            newpermutation[0] = parity
            newresult.append(newpermutation)
      return newresult