Statement

Giorgio is working on a new research paper, this time about integer sequences. Today, he's looking for a specific kind of sequence: the rescaling sequence. A rescaling sequence is a sequence of integers such that, for each pair of adjacent elements, one of the following statements is true: (1) The second element is smaller than the first element. (2) The second element is a multiple of the first element. So, this is a rescaling sequence: 4, 8, 7, 21, 19. This however is not: 4, 8, 7, 20, 19 because 20 is not a multiple of 7. You are given a sequence of N integers. Giorgio can delete some elements from the sequence, but he wants to delete as few as possible of them (possibly zero!). Help Giorgio obtain a rescaling sequence by computing the minimum number of elements to be deleted.