The problem requires us to find the n-th digit in an infinite sequence formed by concatenating all positive integers starting from 1.

Observations:

1. The sequence starts as: 123456789101112131415..., and we need to determine the digit at position (n).

2. A simple way to construct the sequence is to append numbers as strings until we reach the required length.

   Approach:

• Initialize an empty string sequence.
• Iterate from 1 onwards, converting each number to a string and appending it to sequence.
• Stop when sequence reaches at least n characters.

• Print the n-th digit (adjusting for 0-based indexing).

  Complexity Analysis:

  Since numbers grow in length, the loop runs approximately O(sqrt{n}) times, making the approach efficient.

n = int(input())
sequence = ""
for num in range(1, 1000):
    sequence += str(num)
    if len(sequence) >= n:  # You can stop early when sequence is long enough
        break
print(sequence[n - 1])

Anansi needs to arrange 2n A2SVians into two rows: - Front row: Shorter individuals. - Back row: Taller individuals.

Each person in the back row must be at least x units taller than the corresponding person in the front row.

We need to determine if this arrangement is possible for each test case.

Hint 1
How can sorting help in organizing the two rows optimally?

Hint 2
Try to place the smallest n people in the front row and the largest n people in the back row.

Hint 3
After sorting, check if every person in the back row is at least x units taller than their corresponding person in the front row.

Approach

1. Sorting for optimal arrangement

• To maximize our chances of meeting the height requirement, we sort the heights in non-decreasing order.
• Assign:
  • Front row: First n elements.
  • Back row: Last n elements.

1. Checking the Condition

• Ensure that for every j: [ \text{back}[j] — \text{front}[j] \geq x ]
• If all pairs satisfy the condition, print "YES", otherwise print "NO".

for i in range(d, n):  # Slide the window through the array
    window[arr[i]] += 1  # Add new show to window
    window[arr[i - d]] -= 1  # Remove old show from window

    if window[arr[i - d]] == 0:  # Remove show from counter if it no longer exists in window
        del window[arr[i - d]]

    ans = min(ans, len(window))  # Update the minimum unique shows

print(ans)  # Output the result for the test case

</spoiler>






### [E. Equalizing Arrays](https://codeforces.net/gym/588468/problem/E)

<spoiler summary = "Solution">
Let's prove that next greedy solution works: each step we will find prefixes of minimal length of arrays $$$A$$$ and $$$B$$$ such that its sums are equal and we will cut them forming next block. If we will get valid partition in result so it is an optimal solution, otherwise there is no solution. Since length of prefix proportional to its sum, so prefixes are minimal since its sums are
minimal.

Let's prove this algorithm: let optimal solution have alternative partition. Since our solution cuts minimal possible prefixes, so (at some step) optimal solution cuts prefix with greater sum (and greater length). But this prefixes in optimal solutions contain smaller prefixes, found by greedy solution, so it can be divided on two parts — contradiction.

So we can keep prefixes and increase one which have smaller sum.

Time complexity: $$$O(n)$$$.
</spoiler>


<spoiler summary="Code">

import sys

n = int(sys.stdin.readline().strip()) a = list(map(int, sys.stdin.readline().strip().split())) m = int(sys.stdin.readline().strip()) b = list(map(int, sys.stdin.readline().strip().split()))

if sum(a) != sum(b): print(-1) exit()

p1, p2 =0, 0

cur_sum1, cur_sum2 = 0, 0

ans = 0

while p1 < n:

cur_sum1 += a[p1]
cur_sum2 += b[p2]
p1 += 1
p2 += 1

while cur_sum1 != cur_sum2:
    if cur_sum1 < cur_sum2:
        cur_sum1 += a[p1]
        p1 += 1
    else:
        cur_sum2 += b[p2]
        p2 += 1
ans += 1

print(ans) ```