#include <iostream>
using namespace std;
 
int upperBound(int arr[], int n, int x) {
    int low = 0;
    int high = n - 1;
    int ans = n;   // If no element is greater than x
 
    while (low <= high) {
        int mid = low + (high - low) / 2;
 
        if (arr[mid] > x) {
            ans = mid;
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
 
    return ans;
}
 
int main() {
    int arr[] = {1, 2, 4, 4, 6, 8, 10};
    int n = 7;
    int x = 4;
 
    cout << "Upper Bound index = " << upperBound(arr, n, x);
 
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IHVwcGVyQm91bmQoaW50IGFycltdLCBpbnQgbiwgaW50IHgpIHsKICAgIGludCBsb3cgPSAwOwogICAgaW50IGhpZ2ggPSBuIC0gMTsKICAgIGludCBhbnMgPSBuOyAgIC8vIElmIG5vIGVsZW1lbnQgaXMgZ3JlYXRlciB0aGFuIHgKCiAgICB3aGlsZSAobG93IDw9IGhpZ2gpIHsKICAgICAgICBpbnQgbWlkID0gbG93ICsgKGhpZ2ggLSBsb3cpIC8gMjsKCiAgICAgICAgaWYgKGFyclttaWRdID4geCkgewogICAgICAgICAgICBhbnMgPSBtaWQ7CiAgICAgICAgICAgIGhpZ2ggPSBtaWQgLSAxOwogICAgICAgIH0KICAgICAgICBlbHNlIHsKICAgICAgICAgICAgbG93ID0gbWlkICsgMTsKICAgICAgICB9CiAgICB9CgogICAgcmV0dXJuIGFuczsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgYXJyW10gPSB7MSwgMiwgNCwgNCwgNiwgOCwgMTB9OwogICAgaW50IG4gPSA3OwogICAgaW50IHggPSA0OwoKICAgIGNvdXQgPDwgIlVwcGVyIEJvdW5kIGluZGV4ID0gIiA8PCB1cHBlckJvdW5kKGFyciwgbiwgeCk7CgogICAgcmV0dXJuIDA7Cn0=