import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 4, 5, 6};
        int k = 12;
 
        int totalSubarraysCount = 0;
        int currentWindowSum = 0;
        int left = 0;
 
        // 'right' expands the window forward
        for (int right = 0; right < arr.length; right++) {
            currentWindowSum += arr[right];
 
            // If the sum exceeds k, contract the window from the left
            while (currentWindowSum > k && left <= right) {
                currentWindowSum -= arr[left];
                left++;
            }
 
            // O(1) Counting Step: 
            // All valid subarrays ending at 'right' are counted at once.
            int windowSize = right - left + 1;
            totalSubarraysCount += windowSize;
        }
 
        System.out.println("Total subarrays with sum <= k is " + totalSubarraysCount);
    }
}
 

CmltcG9ydCBqYXZhLnV0aWwuKjsKaW1wb3J0IGphdmEubGFuZy4qOwppbXBvcnQgamF2YS5pby4qOwoKY2xhc3MgTWFpbiB7CiAgICBwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgaW50W10gYXJyID0gbmV3IGludFtdezEsIDEsIDEsIDQsIDUsIDZ9OwogICAgICAgIGludCBrID0gMTI7CiAgICAgICAgCiAgICAgICAgaW50IHRvdGFsU3ViYXJyYXlzQ291bnQgPSAwOwogICAgICAgIGludCBjdXJyZW50V2luZG93U3VtID0gMDsKICAgICAgICBpbnQgbGVmdCA9IDA7CgogICAgICAgIC8vICdyaWdodCcgZXhwYW5kcyB0aGUgd2luZG93IGZvcndhcmQKICAgICAgICBmb3IgKGludCByaWdodCA9IDA7IHJpZ2h0IDwgYXJyLmxlbmd0aDsgcmlnaHQrKykgewogICAgICAgICAgICBjdXJyZW50V2luZG93U3VtICs9IGFycltyaWdodF07CgogICAgICAgICAgICAvLyBJZiB0aGUgc3VtIGV4Y2VlZHMgaywgY29udHJhY3QgdGhlIHdpbmRvdyBmcm9tIHRoZSBsZWZ0CiAgICAgICAgICAgIHdoaWxlIChjdXJyZW50V2luZG93U3VtID4gayAmJiBsZWZ0IDw9IHJpZ2h0KSB7CiAgICAgICAgICAgICAgICBjdXJyZW50V2luZG93U3VtIC09IGFycltsZWZ0XTsKICAgICAgICAgICAgICAgIGxlZnQrKzsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgLy8gTygxKSBDb3VudGluZyBTdGVwOiAKICAgICAgICAgICAgLy8gQWxsIHZhbGlkIHN1YmFycmF5cyBlbmRpbmcgYXQgJ3JpZ2h0JyBhcmUgY291bnRlZCBhdCBvbmNlLgogICAgICAgICAgICBpbnQgd2luZG93U2l6ZSA9IHJpZ2h0IC0gbGVmdCArIDE7CiAgICAgICAgICAgIHRvdGFsU3ViYXJyYXlzQ291bnQgKz0gd2luZG93U2l6ZTsKICAgICAgICB9CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiVG90YWwgc3ViYXJyYXlzIHdpdGggc3VtIDw9IGsgaXMgIiArIHRvdGFsU3ViYXJyYXlzQ291bnQpOwogICAgfQp9Cg==