MODULE charaQsortMod
! 文字のクイックソート
! 文字列内の文字を昇順に並び替える．

!!!!!!!!!!!!!!!!!!!  caution  !!!!!!!!!!!!!!!!!!!
! 大文字小文字を併用する場合に注意！！！！
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

      implicit none
      
      interface qSort
        module procedure :: charaQsort
      end interface
      
      contains
!引数，出力は文字列．文字の配列ではない．
      pure recursive function charaQsort( s ) result( r )
        implicit none
        character(*),intent(in) :: s
        character(len(s)) :: r, buff
        character(1) :: buffer(1),sample(3),piv
        integer :: i,j,l,head,tail
        
        l = len( s )
        if( l<=1 )then
          r = s
        else
          !select pivot
          sample(1:3) = [s(1:1), s(l/2:l/2), s(l:l)]
          do i = 1,2
            do j = 2,3
              if( sample(i)>sample(j) )then
                buffer(1:1) = sample(i:i)
                sample(i:i) = sample(j:j)
                sample(j:j) = buffer(1:1)
              end if
            end do
          end do
          piv = sample(2)
          
          head = 1; tail = l; j = 1 !次に代入される場所
          do i = 1,l
            if( s(i:i) < piv )then
              r(head:head) = s(i:i)
              head = head + 1
            else if( s(i:i) >piv )then
              r(tail:tail) = s(i:i)
              tail = tail - 1
            else
              buff(j:j) = s(i:i)
              j = j + 1
            end if
          end do !i
          
          r(1:head-1) = charaQsort( r(1:head-1) )
          r(tail+1:l) = charaQsort( r(tail+1:l) )
          r(head:tail) = buff(1:j)
          
        end if
      end function
      end MODULE charaQsortMod

      MODULE strQsortMod
! 文字列のクイックソート
! charLen で使用可能な文字列サイズの上限を定める．

!!!!!!!!!!!!!!!!!!!  caution  !!!!!!!!!!!!!!!!!!!
! 大文字小文字を併用する場合に注意！！！！
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


!!2020/05/16
!select pivot のとこのバッファ部分おかしくない？後で確認．

      implicit none
      integer(4),parameter,private :: charLen = 10
      
      interface qSort
        module procedure :: strQsort
      end interface
      
      contains
      pure recursive function strQsort( s ) result( r )
        implicit none
        character(charLen), intent(in) :: s(:)
        character(charLen) :: r( size(s) ), sample(3), buffer
        integer(4) :: len, i,j
        
        len = size( s(:) )
        if( len<=1 )then
          r = s
        else
          !select pivot
          sample(1:3) = [s(1), s(len/2), s(len)]
          do i = 1,2
            do j = 2,3
              if( sample(i)>sample(j) )then
                buffer = sample(i)
                sample(i) = sample(j)
                sample(j) = buffer
              end if
            end do
          end do
          
          r = [ strQsort( pack(s(:), s(:)< sample(2)) ), &
                          pack(s(:), s(:)==sample(2))  , &
                strQsort( pack(s(:), s(:)> sample(2)) ) ]
        end if
      end function
      end MODULE strQsortMod

      
      PROGRAM GreenBin
      use charaQsortMod
      use strQsortMod
      IMPLICIT NONE
      integer(16) :: n
      character(10),allocatable :: s(:)
      integer(16) :: i,ans=0,cnt
      character(10) :: buffer
      
      read*,n
      allocate( s(n) )
      do i = 1,n
        read*,s(i)(1:10)
      end do
      
      do i = 1,n
        s(i)(1:10) = qsort( s(i)(1:10) )
      end do
      
      s = qsort( s )
      
      
      buffer = 'AAAAAAAAAA'
      cnt = 0
      do i = 1,n
        if( buffer(1:10)==s(i)(1:10) )then
          cnt = cnt + 1
          ans = ans + cnt
        else
          cnt = 0
        end if
        buffer = s(i)(1:10)
      end do
      
      print*,ans
      
      
    !  print*,n
    !  do i = 1,n
    !    print*,s(i)(1:10)
    !  end do
      
      END PROGRAM
      

Measured memory_bytes: 6064