<|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
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int64_t n;

void read() { cin >> n; }

void solve() {
    // The k-th term 123...k is divisible by 3 exactly when its digit sum, which
    // is 1+2+...+k = k(k+1)/2, is divisible by 3, i.e. when k mod 3 is 0 or 2.
    // So among k = 1..n there are 2 such terms per full block of 3, plus one
    // extra when n mod 3 == 2.

    int64_t answer = n / 3 * 2;
    if(n % 3 == 2) {
        answer++;
    }

    cout << answer << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    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()
```
