Consider the following array:

[1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 12345678910, 1234567891011 ...]

If we join these numbers, you will end up with an infinite sequence:

112123123412345123456 ... to infinity.

Given a number n, return the element at nth index of the sequence. You can assume that the indexes start from 1 (not 0).

Examples

infiniteSequence(1) ➞ 1
// number at index 1 = 1

infiniteSequence(3) ➞ 2
// number at index 3 = 2

infiniteSequence(100) ➞ 1

Notes

1 ≤ n ≤ 10^18