<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

105. Div 3

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


There is sequence 1, 12, 123, 1234, ..., 12345678910, ... . Given first N elements of that sequence. You must determine amount of numbers in it that are divisible by 3.


Input

Input contains N (1<=N<=231 - 1).


Output

Write answer to the output.


Sample Input

4
Sample Output

2

<|response|>
1. Abridged Problem Statement  
   Given a positive integer N (1 ≤ N ≤ 2³¹–1). Define aₖ as the decimal number formed by concatenating “1,2,…,k” (for example, a₄ = 1234). Count how many of a₁, a₂, …, a_N are divisible by 3.

2. Key Observations  
   • A number is divisible by 3 exactly when the sum of its digits is divisible by 3.  
   • When you concatenate 1,2,…,k, the total digit‐sum equals the sum of the digit‐sums of each integer i from 1 to k.  
   • For any integer i, i ≡ digit_sum(i) (mod 3). Therefore  
       digit_sum(aₖ) mod 3 = (∑_{i=1}^k digit_sum(i)) mod 3  
                         = (∑_{i=1}^k i) mod 3  
                         = [k·(k+1)/2] mod 3.  
   • So aₖ is divisible by 3 ⇔ k(k+1)/2 ≡ 0 (mod 3). Since 2 is invertible modulo 3, this is equivalent to  
       k·(k+1) ≡ 0 (mod 3)  
     which holds exactly when k ≡ 0 or 2 (mod 3).

3. Full Solution Approach  
   1. We need to count all k in the range [1..N] with k mod 3 = 0 or 2.  
   2. Partition the integers 1…N into ⌊N/3⌋ full blocks of size 3, plus a remainder r = N mod 3.  
      – In each full block of three consecutive values, exactly two satisfy (k mod 3 ∈ {0,2}).  
      – So from the full blocks we get 2 × ⌊N/3⌋.  
   3. Handle the leftover r values:  
      – If r = 0 → no extra.  
      – If r = 1 → the extra value has k mod 3 = 1 → no extra.  
      – If r = 2 → the two extra values are k mod 3 = 1 and k mod 3 = 2 → one extra.  
   4. Final formula:  
        answer = 2·⌊N/3⌋ + (r == 2 ? 1 : 0).  
   5. All operations are O(1) and fit in 64‐bit arithmetic.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N;
    cin >> N;                         // Read the input N (1 ≤ N ≤ 2^31–1)

    // Count how many full groups of 3 are in [1..N]
    long long full_groups = N / 3;

    // Each group of size 3 contributes exactly 2 valid k's
    long long answer = full_groups * 2;

    // Handle the remainder N mod 3:
    // If remainder is 2, then among the last two numbers
    // one of them has k mod 3 == 2, so we add one more.
    if (N % 3 == 2) {
        answer += 1;
    }

    cout << answer << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys

def main():
    data = sys.stdin.read().strip()
    N = int(data)                 # Read N

    # Number of full blocks of size 3
    full_groups = N // 3

    # Each full block contributes exactly 2 valid k's
    answer = full_groups * 2

    # If there are 2 leftover values, one of them has k mod 3 == 2
    if N % 3 == 2:
        answer += 1

    # Print the result
    print(answer)

if __name__ == "__main__":
    main()
```