When a number is written in base 10,   adjacent digits may "rise" or "fall" as the number is read   (usually from left to right).



Definition

Given the decimal digits of the number are written as a series   d:

   A   rise   is an index   i   such that    d(i)  <  d(i+1)
   A   fall    is an index   i   such that    d(i)  >  d(i+1)


Examples

   The number   726,169   has   3   rises and   2   falls,   so it isn't in the sequence.
   The number     83,548   has   2   rises and   2   falls,   so it   is   in the sequence.


Task

   Print the first   200   numbers in the sequence 
   Show that the   10 millionth   (10,000,000th)   number in the sequence is   41,909,002


See also

   OEIS Sequence  A296712   describes numbers whose digit sequence in base 10 have equal "rises" and "falls".


Related tasks

   Esthetic numbers


with Ada.Text_Io;
with Ada.Integer_Text_Io;
 
procedure Equal_Rise_Fall is
   use Ada.Text_Io;
 
   function Has_Equal_Rise_Fall (Value : Natural) return Boolean is
      Rises : Natural := 0;
      Falls : Natural := 0;
      Image : constant String := Natural'Image (Value);
      Last  : Character := Image (Image'First + 1);
   begin
      for Pos in Image'First + 2 .. Image'Last loop
         if Image (Pos) > Last then
            Rises := Rises + 1;
         elsif Image (Pos) < Last then
            Falls := Falls + 1;
         end if;
         Last := Image (Pos);
      end loop;
      return Rises = Falls;
   end Has_Equal_Rise_Fall;
 
   Value : Natural := 1;
   Count : Natural := 0;
begin
   loop
      if Has_Equal_Rise_Fall (Value) then
         Count := Count + 1;
         if Count <= 200 then
            Ada.Integer_Text_Io.Put (Value, Width => 5);
            if Count mod 20 = 0 then
               New_Line;
            end if;
         end if;
         if Count = 10_000_000 then
            New_Line;
            Put_Line ("The 10_000_000th: " & Natural'Image (Value));
            exit;
         end if;
      end if;
      Value := Value + 1;
   end loop;
end Equal_Rise_Fall;