program fannkuch
use iso_fortran_env
implicit none
character(len=256) :: line
integer, parameter :: max_n = 12
integer :: p(max_n), c(max_n), tmp
integer :: i, j, n
integer :: flip_count, max_count
integer :: checksum
integer :: coef
integer, external :: flip

call get_command_argument(1,line)
read(line,'(i2)') n
if (n < 3 .or. n > 12) then
  stop 'please use 3 <= n <= 12'
end if

! set p = 1 2 3 ... n
do i = 1, n
  p(i) = i
end do

coef = 1
flip_count = 0
max_count = 0
checksum = 0

c = 1
i = 2
do while (i.le.n)
  ! rotate first i elements of p
  tmp = p(1)
  do j = 2, i
    p(j-1) = p(j)
  end do
  p(i) = tmp
  ! check if valid permutation
  if (c(i).lt.i) then
    c(i) = c(i) + 1
    i = 2
    coef = -coef
    ! use permutation p
    flip_count = flip(p,n)
    max_count = max(max_count,flip_count)
    checksum = checksum + coef * flip_count
  else
    c(i) = 1
    i = i + 1
  end if
end do

write(line,'(i15)') checksum
write(*,'(a)') trim(adjustl(line))
write(line,'(i15)') n
write(*,'(3a,i3)') 'Pfannkuchen(',trim(adjustl(line)),') =',max_count

end program

pure integer function flip(p,n)
implicit none
integer, intent(in) :: n
integer, intent(in) :: p(n)
integer, parameter :: max_n = 12
integer :: perm(max_n), tmp
integer :: i, j, lead, half
flip = 0
lead = p(1)
if (lead.eq.1) return
if (p(lead).eq.1) then
  flip = 1
  return
end if

! slow with -O3/-Ofast, but fast with -check arg_temp_created or with -O2
perm(1:n)=p(1:n)

! always faster
!do i=1,n
!  perm(i)=p(i)
!end do

do while (lead.ne.1)
  i=1
  j=lead
  do while (i.lt.j)
    tmp = perm(i)
    perm(i)=perm(j)
    i = i + 1
    perm(j)=tmp
    j = j - 1
  end do
  flip = flip + 1
  lead = perm(1)
end do
end function
