import java.util.Arrays;
 
public class Main {
    public static void main(String[] args) {
        int n = 5; // size of the array
        int[] a = {6, 7, 3, 2, 2};
 
        int[] dp = new int[n + 1]; // dp array
        int i = 0;
        while (i <= n - 1) {
            if (i == 0) {
                dp[i] = a[i];
            } else {
                dp[i] = a[i] + dp[i - 1];
            }
            i++;
        }
 
        int q = 4; // number of queries
        int[] w = {0, 3, 4, 2}; // query array
        i = 0;
        while (i <= q - 1) {
            int query = w[i];
            System.out.println(dp[query]); // answering each query in O(1)
            i++;
        }
    }
}

aW1wb3J0IGphdmEudXRpbC5BcnJheXM7CiAKcHVibGljIGNsYXNzIE1haW4gewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGludCBuID0gNTsgLy8gc2l6ZSBvZiB0aGUgYXJyYXkKICAgICAgICBpbnRbXSBhID0gezYsIDcsIDMsIDIsIDJ9OwogCiAgICAgICAgaW50W10gZHAgPSBuZXcgaW50W24gKyAxXTsgLy8gZHAgYXJyYXkKICAgICAgICBpbnQgaSA9IDA7CiAgICAgICAgd2hpbGUgKGkgPD0gbiAtIDEpIHsKICAgICAgICAgICAgaWYgKGkgPT0gMCkgewogICAgICAgICAgICAgICAgZHBbaV0gPSBhW2ldOwogICAgICAgICAgICB9IGVsc2UgewogICAgICAgICAgICAgICAgZHBbaV0gPSBhW2ldICsgZHBbaSAtIDFdOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGkrKzsKICAgICAgICB9CiAKICAgICAgICBpbnQgcSA9IDQ7IC8vIG51bWJlciBvZiBxdWVyaWVzCiAgICAgICAgaW50W10gdyA9IHswLCAzLCA0LCAyfTsgLy8gcXVlcnkgYXJyYXkKICAgICAgICBpID0gMDsKICAgICAgICB3aGlsZSAoaSA8PSBxIC0gMSkgewogICAgICAgICAgICBpbnQgcXVlcnkgPSB3W2ldOwogICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50bG4oZHBbcXVlcnldKTsgLy8gYW5zd2VyaW5nIGVhY2ggcXVlcnkgaW4gTygxKQogICAgICAgICAgICBpKys7CiAgICAgICAgfQogICAgfQp9