


"""simple docstring"""






class 							A_      :


  def __init__(			self:						Dict							,__lowerCAmelCase:						List[Any]							,__lowerCAmelCase:						Union[str, Any]    ):







     '''simple docstring'''







     _lowerCamelCase   :				int							=     name
     _lowerCamelCase   :				int							=     val


  def __str__(			self:						str    ):







     '''simple docstring'''







     return F"""{self.__class__.__name__}({self.name}, {self.val})"""






  def __lt__(			self:						Dict							,__lowerCAmelCase:						Any    ):







     '''simple docstring'''







     return self.val < other.val




class 							A_      :


  def __init__(			self:						Union[str, Any]							,__lowerCAmelCase:						Union[str, Any]    ):







     '''simple docstring'''







     _lowerCamelCase   :				Optional[int]							=     {}
     _lowerCamelCase   :				List[str]							=     {}
     _lowerCamelCase   :				Union[str, Any]							=     self.build_heap(__lowerCAmelCase    )


  def __getitem__(			self:						int							,__lowerCAmelCase:						Dict    ):







     '''simple docstring'''







     return self.get_value(__lowerCAmelCase    )


  def 							_lowercase					(			self:						Any							,__lowerCAmelCase:						Tuple    ):







     '''simple docstring'''







     return (idx - 1) // 2


  def 							_lowercase					(			self:						int							,__lowerCAmelCase:						Union[str, Any]    ):







     '''simple docstring'''







     return idx * 2 + 1


  def 							_lowercase					(			self:						Optional[int]							,__lowerCAmelCase:						int    ):







     '''simple docstring'''







     return idx * 2 + 2


  def 							_lowercase					(			self:						int							,__lowerCAmelCase:						str    ):







     '''simple docstring'''







     return self.heap_dict[key]


  def 							_lowercase					(			self:						Any							,__lowerCAmelCase:						Optional[Any]    ):







     '''simple docstring'''







     _lowerCamelCase   :				Optional[int]							=     len(__lowerCAmelCase    ) - 1
     _lowerCamelCase   :				List[str]							=     self.get_parent_idx(__lowerCAmelCase    )

     for idx, i in enumerate(__lowerCAmelCase    ):
        _lowerCamelCase   :				Dict							=     idx
        _lowerCamelCase   :				Optional[int]							=     i.val

     for i in range(__lowerCAmelCase							,-1							,-1    ):
        self.sift_down(__lowerCAmelCase							,__lowerCAmelCase    )
     return array


  def 							_lowercase					(			self:						Union[str, Any]							,__lowerCAmelCase:						Union[str, Any]							,__lowerCAmelCase:						int    ):







     '''simple docstring'''







     while True:
        _lowerCamelCase   :				List[Any]							=     self.get_left_child_idx(__lowerCAmelCase    )  # noqa: E741
        _lowerCamelCase   :				Optional[int]							=     self.get_right_child_idx(__lowerCAmelCase    )

        _lowerCamelCase   :				List[str]							=     idx
        if l < len(__lowerCAmelCase    ) and array[l] < array[idx]:
           _lowerCamelCase   :				Tuple							=     l
        if r < len(__lowerCAmelCase    ) and array[r] < array[smallest]:
           _lowerCamelCase   :				List[Any]							=     r

        if smallest != idx:
           _lowerCamelCase,					_lowerCamelCase   :				Optional[Any]							=     array[smallest], array[idx]
           (
               (
               _lowerCamelCase
           ),					(
               _lowerCamelCase
           ),					
           )   :				Tuple							=     (
               self.idx_of_element[array[smallest]],
               self.idx_of_element[array[idx]],
           )
           _lowerCamelCase   :				Tuple							=     smallest
        else:
           break


  def 							_lowercase					(			self:						Union[str, Any]							,__lowerCAmelCase:						str    ):







     '''simple docstring'''







     _lowerCamelCase   :				List[str]							=     self.get_parent_idx(__lowerCAmelCase    )
     while p >= 0 and self.heap[p] > self.heap[idx]:
        _lowerCamelCase,					_lowerCamelCase   :				Tuple							=     self.heap[idx], self.heap[p]
        _lowerCamelCase,					_lowerCamelCase   :				Tuple							=     (
            self.idx_of_element[self.heap[idx]],
            self.idx_of_element[self.heap[p]],
        )
        _lowerCamelCase   :				Tuple							=     p
        _lowerCamelCase   :				Optional[Any]							=     self.get_parent_idx(__lowerCAmelCase    )


  def 							_lowercase					(			self:						Union[str, Any]    ):







     '''simple docstring'''







     return self.heap[0]


  def 							_lowercase					(			self:						Tuple    ):







     '''simple docstring'''







     _lowerCamelCase,					_lowerCamelCase   :				List[str]							=     self.heap[-1], self.heap[0]
     _lowerCamelCase,					_lowerCamelCase   :				Optional[Any]							=     (
         self.idx_of_element[self.heap[-1]],
         self.idx_of_element[self.heap[0]],
     )

     _lowerCamelCase   :				Optional[int]							=     self.heap.pop()
     del self.idx_of_element[x]
     self.sift_down(0							,self.heap    )
     return x


  def 							_lowercase					(			self:						Tuple							,__lowerCAmelCase:						str    ):







     '''simple docstring'''







     self.heap.append(__lowerCAmelCase    )
     _lowerCamelCase   :				str							=     len(self.heap    ) - 1
     _lowerCamelCase   :				str							=     node.val
     self.sift_up(len(self.heap    ) - 1    )


  def 							_lowercase					(			self:						Any    ):







     '''simple docstring'''







     return len(self.heap    ) == 0






  def 							_lowercase					(			self:						List[str]							,__lowerCAmelCase:						str							,__lowerCAmelCase:						List[str]    ):







     '''simple docstring'''







     assert (
         self.heap[self.idx_of_element[node]].val > new_value
     ), "newValue must be less that current value"
     _lowerCamelCase   :				List[str]							=     new_value
     _lowerCamelCase   :				Union[str, Any]							=     new_value
     self.sift_up(self.idx_of_element[node]    )


_lowerCAmelCase							:    int					   =	Node('''R''', -1)
_lowerCAmelCase							:    List[Any]					   =	Node('''B''', 6)
_lowerCAmelCase							:    List[str]					   =	Node('''A''', 3)
_lowerCAmelCase							:    Optional[int]					   =	Node('''X''', 1)
_lowerCAmelCase							:    str					   =	Node('''E''', 4)

# Use one of these two ways to generate Min-Heap

# Generating Min-Heap from array
_lowerCAmelCase							:    Tuple					   =	MinHeap([r, b, a, x, e])

# Generating Min-Heap by Insert method
# myMinHeap.insert(a)
# myMinHeap.insert(b)
# myMinHeap.insert(x)
# myMinHeap.insert(r)
# myMinHeap.insert(e)

# Before
print('''Min Heap - before decrease key''')
for i in my_min_heap.heap:
  print(i)

print('''Min Heap - After decrease key of node [B -> -17]''')
my_min_heap.decrease_key(b, -17)

# After
for i in my_min_heap.heap:
  print(i)

if __name__ == "__main__":
  import doctest

  doctest.testmod()



'''simple docstring'''






def    _snake_case  (	A			)		->       int:
							if n == 1 or not isinstance(A					,       A			):
														return 0
							elif n == 2:
														return 1
							else:
														lowerCAmelCase__			  =      [0, 1]
														for i in range(2					,       n + 1			):
																					sequence.append(sequence[i - 1] + sequence[i - 2]			)

														return sequence[n]


def    _snake_case  (	A			)		->       int:
							lowerCAmelCase__			  =      0
							lowerCAmelCase__			  =      2

							while digits < n:
														index += 1
														lowerCAmelCase__			  =      len(str(fibonacci(A			)			)			)

							return index


def    _snake_case  (	A = 1000			)		->       int:
							return fibonacci_digits_index(A			)


if __name__ == "__main__":
		print(solution(int(str(input()).strip())))