Out of Sorts (Gold)

Keeping an eye on long-term career opportunities beyond the farm, Bessie the cow has started learning algorithms on various online coding websites.

Her favorite algorithm so far is "bubble sort". Here is Bessie's initial implementation, in cow-code, for sorting an array $A$ of length $n$:

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Apparently, the "moo" command in cow-code does nothing except print "moo". Strangely, Bessie insists on including it at various places in her code.

After testing her code on several arrays, Bessie makes an interesting observation: while large elements move to the end of the array very quickly, small elements can take a very long time to "bubble" to the front (she suspects this is how the algorithm got its name). To alleviate this problem, Bessie modifies her code so that each iteration of the main loop scans the array forward and then backward, giving both large and small elements a chance to move long distances in a single iteration. Her code now looks like this:

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = n-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to n-2:
      if A[i+1] < A[i]:
         sorted = false

Given the input array, predict how many times Bessie's modified code will print "moo".