ExpertData Analysis50 points

Anomalies that do not poison the baseline

A payment gateway in Stockholm measures response latency every minute. The on-call engineer wants alerts when a reading is far from normal behaviour. A naive rolling window gets contaminated: once a spike enters it, the baseline widens and later spikes pass unnoticed. The fix is to build the baseline only from readings that were accepted as normal.

Task: line 1 is w k (an integer window size and a decimal multiplier). Line 2 holds the readings (numbers, 1-indexed). The first w readings are accepted as normal automatically. For every later reading x, take the last w accepted readings (not the last w raw ones), compute their mean and population standard deviation s. If s is 0, the reading is an anomaly when x differs from the mean. Otherwise it is an anomaly when |x - mean| > k * s (strictly greater). An anomaly is reported and is not added to the accepted readings; a normal reading is added. Print Anomalies: i1 i2 ... with the 1-based positions of the anomalies in order, or Anomalies: none. On a second line print Accepted: N, the number of accepted readings in the end.

Sample tests

Input

5 3
100 102 99 101 100 103 450 101 98 520 102 99 100 600 101

Expected output

Anomalies: 7 10 14
Accepted: 12

Input

3 2
10 11 9 10 12 10 11

Expected output

Anomalies: 5 7
Accepted: 5

Your answer is also checked against 4 hidden tests.

Need a hint?

Maintain a separate list of accepted values and slice its tail for the window.