Permutation? Permutatino! Specifications

Your program must can take in an integer n, then take in n more strings (containing only alphanumeric characters) in your preferred method (separated by whitespace, file input, hash table etc.). You must then find the permutation before the inputted strings when sorted in lexicographical order, and output that in your preferred method. 

If it is already sorted in lexicographical order, output the permutation in reverse regular lexicographical order.

Rules

1) Code can be just a function

2) If you pipe in from a file, you can to exclude the file name's length from your program (just the filename, not full path)

3) If there are repeated characters, take the permutation before the first occurrence of the repeats

Test cases

3 abc hi def


The possible permutations of this (in lexicographical order) are:

abc def hi
abc hi def
def abc hi
def hi abc
hi abc def
hi def abc


Now see that abc hi def is the 2nd permutation, so we output abc def hi.

If instead we pick abc def hi(the first permutation), then output abc def hi.

Another test case is in the title: your function should map Permutation to Permutatino

Scoring:

The winner is the code with the smallest score, which is the length of the code multiplied by the bonus.

Bonus:

20% -90% (to keep non-esolangs in the fight) of your byte count if you can do this in O(N) time.

-50% (stacks with the above -90% to give a total of -95%) if your solution isn't O(N!) which is listing out permutations, finding the element and getting the index, subtracting 1 from the index (keep it the same if the index is 0) and outputting the element with the subtracted index

With the above 2 bonuses, I won't be surprised if there's a 2 byte answer.

Hint: there is definitely a faster way to do this apart from listing all the permutations and finding the supposed element in the general case

Congrats to @Forty3 for being the first person to get the O(N) solution!

Here's some (C based) pseudocode:

F(A) { // A[0..n-1] stores a permutation of {1, 2, .., n}
  int i, j;
  for (i = n - 1; i &gt; 0 &amp;&amp; (A[i-1] &lt; A[i]); i--)
    ; // empty statement
  if (i = 0)
    return 0;
  for (j = i + 1; j &lt; n &amp;&amp; (A[i-1] &gt; A[j]); j++)
    ; // empty statement
  swap(A[i-1], A[j-1]); // swap values in the two entries
  reverse(A[i..n-1]); // reverse entries in the subarray
  return 1;
}


If you want to test if your program is O(N), try with n=11 and the strings being the individual letters of Permutation. If it takes longer than a second, it's most definitely not O(N).
Python 2, 118 96 - 50% = 48 bytes

Takes input in the form ['abc','def','ghi']. Note that this solution returns the list reversed if the input is sorted, as per a previous spec.



def f(n):m=n[1:];S=sorted;a=S(n);return[a.pop(a.index(n[0])-1)]+a[::-1]if m==S(m)else[n[0]]+f(m)


Try it Online!

Seems to be the O(n) solution more efficient than computing all permutations. 

Explanation: Recursively checks if everything after the current element is in sorted order. If so, returns the string immediately lexicographically before (a.index(n[0])-1)) the first element + the rest of the list reversed (a[::-1]).

Runtime: O(n^2 logn) In the worst case (list is reversed), the function will call sorted, which has a runtime of nlogn, for each element in the list (n times).