' Water collected between towers
DECLARE SUB ShellSort (A() AS ANY)
TYPE TTowerRec
  Hght AS INTEGER
  Posi AS INTEGER
END TYPE

'heights of towers in each city prefixed by the number of towers
DATA 5, 1, 5, 3, 7, 2
DATA 10, 5, 3, 7, 2, 6, 4, 5, 9, 1, 2
DATA 16, 2, 6, 3, 5, 2, 8, 1, 4, 2, 2, 5, 3, 5, 7, 4, 1
DATA 4, 5, 5, 5, 5
DATA 4, 5, 6, 7, 8
DATA 4, 8, 7, 7, 6
DATA 5, 6, 7, 10, 7, 6

REM $DYNAMIC
DIM Manhattan(0 TO 1) AS TTowerRec
FOR I% = 1 TO 7
  READ N%
  ERASE Manhattan
  REDIM Manhattan(0 TO N% - 1) AS TTowerRec
  FOR J% = 0 TO N% - 1
    READ Manhattan(J%).Hght
    Manhattan(J%).Posi = J%
  NEXT J%
  ShellSort Manhattan()
  IF Manhattan(0).Posi < Manhattan(1).Posi THEN
    First% = Manhattan(0).Posi
    Last% = Manhattan(1).Posi
  ELSE
    First% = Manhattan(1).Posi
    Last% = Manhattan(0).Posi
  END IF
  Water% = Manhattan(1).Hght * (Last% - First% - 1)
  FOR J% = 2 TO N% - 1
    IF First% < Manhattan(J%).Posi AND Manhattan(J%).Posi < Last% THEN Water% = Water% - Manhattan(J%).Hght
    IF Manhattan(J%).Posi < First% THEN
      Water% = Water% + Manhattan(J%).Hght * (First% - Manhattan(J%).Posi - 1)
      First% = Manhattan(J%).Posi
    END IF
    IF Manhattan(J%).Posi > Last% THEN
      Water% = Water% + Manhattan(J%).Hght * (Manhattan(J%).Posi - Last% - 1)
      Last% = Manhattan(J%).Posi
    END IF
  NEXT J%
  PRINT USING "City configuration ## collected #### units of water."; I%; Water%
NEXT I%
END

REM $STATIC
SUB ShellSort (A() AS TTowerRec)
  'quick and dirty shellsort, not the focus of this exercise
  Gap% = UBOUND(A): N% = UBOUND(A)
  DIM Temp AS TTowerRec
  DO
    Gap% = INT(Gap% / 2.2)
    IF Gap% = 0 THEN Gap% = 1
    FOR I% = Gap% TO N%
      Temp = A(I%)
      J% = I%
      ' Simulated WHILE J% >= Gap% ANDALSO A(J% - Gap%).Hght < Temp.Hght
      DO
        IF J% < Gap% THEN EXIT DO
        IF A(J% - Gap%).Hght >= Temp.Hght THEN EXIT DO
        A(J%) = A(J% - Gap%)
        J% = J% - Gap%
      LOOP
      A(J%) = Temp
    NEXT I%
  LOOP UNTIL Gap% = 1
END SUB